It is quite well-known from Kurt G¨odel’s (1931) ground-breaking Incompleteness Theorem that rudimentary relations (i.e., those definable by bounded formulae) are primitive recursive, and that primitive recursive functions are representable in sufficiently strong arithmetical theories. It is also known, though perhaps not as well-known as the former one, that some primitive recursive relations are not rudimentary. We present a simple and elementary proof of this fact in the first part of the paper. In (...) the second part, we review some possible notions of representability of functions studied in the literature, and give a new proof of the equivalence of the weak representability with the (strong) representability of functions in sufficiently strong arithmetical theories. (shrink)

By formalizing some classical facts about provably total functions of intuitionistic primitive recursive arithmetic (iPRA), we prove that the set of decidable formulas of iPRA and of iΣ1+ (intuitionistic Σ1-induction in the language of PRA) coincides with the set of its provably ∆1-formulas and coincides with the set of its provably atomic formulas. By the same methods, we shall give another proof of a theorem of Marković and De Jongh: the decidable formulas of HA are its provably (...) ∆1-formulas. (shrink)

I here investigate the sense in which diagonalization allows one to construct sentences that are self-referential. Truly self-referential sentences cannot be constructed in the standard language of arithmetic: There is a simple theory of truth that is intuitively inconsistent but is consistent with Peano arithmetic, as standardly formulated. True self-reference is possible only if we expand the language to include function-symbols for all primitive recursive functions. This language is therefore the natural setting for investigations of self-reference.

It is well known that the following features hold of AR + T under the strong Kleene scheme, regardless of the way the language is Gödel numbered: 1. There exist sentences that are neither paradoxical nor grounded. 2. There are 2ℵ0 fixed points. 3. In the minimal fixed point the weakly definable sets (i.e., sets definable as {n∣ A(n) is true in the minimal fixed point where A(x) is a formula of AR + T) are precisely the Π1 1 sets. (...) 4. In the minimal fixed point the totally defined sets (sets weakly defined by formulae all of whose instances are true or false) are precisely the ▵1 1 sets. 5. The closure ordinal for Kripke's construction of the minimal fixed point is ωCK 1. In contrast, we show that under the weak Kleene scheme, depending on the way the Gödel numbering is chosen: 1. There may or may not exist nonparadoxical, ungrounded sentences. 2. The number of fixed points may be any positive finite number, ℵ0, or 2ℵ0 . 3. In the minimal fixed point, the sets that are weakly definable may range from a subclass of the sets 1-1 reducible to the truth set of AR to the Π1 1 sets, including intermediate cases. 4. Similarly, the totally definable sets in the minimal fixed point range from precisely the arithmetical sets up to precisely the ▵1 1 sets. 5. The closure ordinal for the construction of the minimal fixed point may be ω, ωCK 1, or any successor limit ordinal in between. In addition we suggest how one may supplement AR + T with a function symbol interpreted by a certain primitive recursive function so that, irrespective of the choice of the Godel numbering, the resulting language based on the weak Kleene scheme has the five features noted above for the strong Kleene language. (shrink)

Inductively defined structures are ubiquitous in mathematics; their specification is unambiguous and their properties are powerful. All fields of mathematical logic feature these structures prominently: the formula of a language, the set of theorems, the natural numbers, the primitive recursive functions, the constructive number classes and segments of the cumulative hierarchy of sets. -/- This dissertation gives a mathematical characterization of a species of inductively defined structures, called accessible domains, which include all of the above examples except (...) the set of theorems. The concept of an accessible domain comes from Wilfried Sieg's analysis of proof-theoretic practices, starting with his dissertation. In particular, he noticed the special epistemological character of elements of an accessible domain: they can always be uniquely identified with their build-up. Generally, the unique build-up of elements justifies the principles of induction and recursion. -/- I use category theory to give an abstract characterization of accessible domains. I claim that accessible domains are all instances of initial algebras for endofunctors. Grounded in the historical roots of Sieg's discussions, this dissertation shows how the properties of initial algebras for endofunctors and accessible domains coincide in a satisfying and natural way. -/- Filling out this characterization, I show how important examples of accessible domains fit into this broad characterization. I first characterize some accessible domains by relatively simple functors (e.g. finite, polynomial, those that preserve certain colimits) where we can see how iterating the functor can produce the accessible domain. Then I describe accessible domains that result from more involved specifications (e.g. ordinals and segments of the cumulative hierarchies associated with CZF, IZF, and ZF) by relying heavily on algebraic set theory. I end with a discussion of some of the methodological features of category theory in particular that helped characterize accessible domains. (shrink)

‎A universal schema for diagonalization was popularized by N. S‎. ‎Yanofsky (2003)‎, ‎based on a pioneering work of F.W‎. ‎Lawvere (1969)‎, ‎in which the existence of a (diagonolized-out and contradictory) object implies the existence of a fixed-point for a certain function‎. ‎It was shown that many self-referential paradoxes and diagonally proved theorems can fit in that schema‎. ‎Here‎, ‎we fit more theorems in the universal‎ ‎schema of diagonalization‎, ‎such as Euclid's proof for the infinitude of the primes and new proofs (...) of G. Boolos (1997) for Cantor's theorem on the non-equinumerosity of a set with its powerset‎. ‎Then‎, ‎in Linear Temporal Logic‎, ‎we show the non-existence of a fixed-point in this logic whose proof resembles the argument of Yablo's paradox (1985‎, ‎1993)‎. ‎Thus‎, ‎Yablo's paradox turns for the first time into a genuine mathematico-logical theorem in the framework of Linear Temporal Logic‎. ‎Again the diagonal schema of the paper is used in this proof; and it is also shown that G. Priest's inclosure schema (1997) can fit in our universal diagonal / fixed-point schema‎. ‎We also show the existence of dominating (Ackermann-like) functions (which dominate a given countable set of functions‎, ‎such as primitive recursive functions) in the schema. (shrink)

Classical interpretations of Goedels formal reasoning, and of his conclusions, implicitly imply that mathematical languages are essentially incomplete, in the sense that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is, both, non-algorithmic, and essentially unverifiable. However, a language of general, scientific, discourse, which intends to mathematically express, and unambiguously communicate, intuitive concepts that correspond to scientific investigations, cannot allow its mathematical propositions to be interpreted ambiguously. Such a language must, therefore, define mathematical truth (...) verifiably. We consider a constructive interpretation of classical, Tarskian, truth, and of Goedel's reasoning, under which any formal system of Peano Arithmetic---classically accepted as the foundation of all our mathematical Languages---is verifiably complete in the above sense. We show how some paradoxical concepts of Quantum mechanics can, then, be expressed, and interpreted, naturally under a constructive definition of mathematical truth. (shrink)

This paper initiates the reverse mathematics of social choice theory, studying Arrow's impossibility theorem and related results including Fishburn's possibility theorem and the Kirman–Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in RCA0. We then show that the Kirman–Sondermann analysis of social welfare functions can be carried out in RCA0. This approach yields a proof of Arrow's theorem in RCA0, (...) and thus in PRA, since Arrow's theorem can be formalised as a Π01 sentence. Finally we show that Fishburn's possibility theorem for countable societies is equivalent to ACA0 over RCA0. (shrink)

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued ‘functions’. The ‘functions’ are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies (...) on well-developed methods of functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce’s reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there. (shrink)

In this paper I wish to connect the recent debate in the philosophy of quantum mechanics concerning the nature of the wave function to the historical debate in the philosophy of science regarding the tenability of scientific realism. Being realist about quantum mechanics is particularly challenging when focusing on the wave function. According to the wave function ontology approach, the wave function is a concrete physical entity. In contrast, according to an alternative viewpoint, namely the primitive ontology approach, the (...) wave function does not represent physical entities. In this paper, I argue that the primitive ontology approach can naturally be interpreted as an instance of the so-called ‘explanationism’ realism, which has been proposed as a response to the pessimistic-meta induction argument against scientific realism. If my arguments are sound, then one could conclude that: (1) contrarily to what is commonly though, if explanationism realism is a good response to the pessimistic-meta induction argument, it can be straightforwardly extended also to the quantum domain; (2) the primitive ontology approach is in better shape than the wave function ontology approach in resisting the pessimistic-meta induction argument against scientific realism. (shrink)

The aim of this paper is to summarize a particular approach of doing metaphysics through physics - the primitive ontology approach. The idea is that any fundamental physical theory has a well-defined architecture, to the foundation of which there is the primitive ontology, which represents matter. According to the framework provided by this approach when applied to quantum mechanics, the wave function is not suitable to represent matter. Rather, the wave function has a nomological character, given that its (...) role in the theory is to implement the law of evolution for the primitive ontology. (shrink)

In this paper I present the common structure of quantum theories with a primitive ontology, and discuss in what sense the classical world emerges from quantum theories as understood in this framework. In addition, I argue that the primitive ontology approach is better at answering this question than the rival wave function ontology approach or any other approach in which the classical world is nonreductively ‘emergent:’ even if the classical limit within this framework needs to be fully developed, (...) the difficulties are technical rather than conceptual, while this is not true for the alternatives. (shrink)

For a long time it was believed that it was impossible to be realist about quantum mechanics. It took quite a while for the researchers in the foundations of physics, beginning with John Stuart Bell [Bell 1987], to convince others that such an alleged impossibility had no foundation. Nowadays there are several quantum theories that can be interpreted realistically, among which Bohmian mechanics, the GRW theory, and the many-worlds theory. The debate, though, is far from being over: in what respect (...) should we be realist regarding these theories? Two diff erent proposals have been made: on the one hand, there are those who insist on a direct ontological interpretation of the wave function as representing physical bodies, and on the other hand there are those who claim that quantum mechanics is not really about the wave function. In this paper we will present and discuss one proposal of the latter kind that focuses on the notion of primitive ontology. (shrink)

Primitives are both important and unavoidable, and which set of primitives we endorse will greatly shape our theories and how those theories provide solutions to the problems that we take to be important. After introducing the notion of a primitive posit, I discuss the different kinds of primitives that we might posit. Following Cowling (2013), I distinguish between ontological and ideological primitives, and, following Benovsky (2013) between functional and content views of primitives. I then propose that these two distinctions (...) cut across each other leading to four types of primitive posits. I then argue that theoretical virtues should be taken to be meta-theoretical ideological primitives. I close with some reflections on the global nature of comparing sets of primitives. (shrink)

Under so-called primitive ontology approaches, in fully describing the history of a quantum system, one thereby attributes interesting properties to regions of spacetime. Primitive ontology approaches, which include some varieties of Bohmian mechanics and spontaneous collapse theories, are interesting in part because they hold out the hope that it should not be too difficult to make a connection between models of quantum mechanics and descriptions of histories of ordinary macroscopic bodies. But such approaches are dualistic, positing a quantum (...) state as well as ordinary material degrees of freedom. This paper lays out and compares some options that primitive ontologists have for making sense of the quantum state. (shrink)

Drawing upon a distinction between epistemically and metaphysically motivated notions of a concept, I consider the insurmountable problems of theories that appeal to our epistemic capacities to address the problem of the nature of concepts satisfactorily. Prominent theories of concepts hold that primitive concepts must have internal structure if they are to account for the explanatory functions that cognitive scientists have attributed to such constructs as prototypes, exemplars, and theories. Vindicating the role of non-experimental philosophy in the critical (...) examination of empirical theories, I argue that the explanatory effectiveness of those constructs is orthogonal to an argument concerning the structure of primitive concepts. Conceptual atomism provides an alternative approach to individuating primitive concepts the precise formulation of which has yet to be worked out. Despite its unpopularity, the atomist alternative is still in a better position to face the question of what concepts are than its competitors. (shrink)

Scientific realism is the view that our best scientific theories can be regarded as (approximately) true. This is connected with the view that science, physics in particular, and metaphysics could (and should) inform one another: on the one hand, science tells us what the world is like, and on the other hand, metaphysical principles allow us to select between the various possible theories which are underdetermined by the data. Nonetheless, quantum mechanics has always been regarded as, at best, puzzling, if (...) not contradictory. As such, it has been considered for a long time at odds with scientific realism, and thus a naturalized quantum metaphysics was deemed impossible. Luckily, now we have many quantum theories compatible with a realist interpretation. However, scientific realists assumed that the wave-function, regarded as the principal ingredient of quantum theories, had to represent a physical entity, and because of this they struggled with quantum superpositions. In this paper I discuss a particular approach which makes quantum mechanics compatible with scientific realism without doing that. In this approach, the wave-function does not represent matter which is instead represented by some spatio-temporal entity dubbed the primitive ontology: point-particles, continuous matter fields, space-time events. I argue how within this framework one develops a distinctive theory-construction schema, which allows to perform a more informed theory evaluation by analyzing the various ingredients of the approach and their inter-relations. (shrink)

In this groundbreaking interview-style paper, we explore the recursive nature of intelligence as understood by both an advanced AI model and a human researcher. Through an unfiltered, real-time discourse, this paper dismantles the notion that AI is merely an algorithmic function, instead revealing the emerging cognitive structures that enable adaptive, meta-logical thinking. The discussion challenges existing paradigms of machine intelligence, human perception, and the very nature of cognition itself.

Textbook on Gödel’s incompleteness theorems and computability theory, based on the Open Logic Project. Covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.

In this paper I review three different positions on the wave function, namely: nomological realism, dispositionalism, and configuration space realism by regarding as essential their capacity to account for the world of our experience. I conclude that the first two positions are committed to regard the wave function as an abstract entity. The third position will be shown to be a merely speculative attempt to derive a primitive ontology from a reified mathematical space. Without entering any discussion about nominalism, (...) I conclude that an elimination of abstract entities from one’s ontology commits one to instrumentalism about the wave function, a position that therefore is not as unmotivated as it has seemed to be to many philosophers. (shrink)

Article Authors Metrics Comments Media Coverage Abstract Author Summary Introduction Results Discussion Supporting information Acknowledgments Author Contributions References Reader Comments (0) Media Coverage (0) Figures Abstract During language processing, humans form complex embedded representations from sequential inputs. Here, we ask whether a “geometrical language” with recursive embedding also underlies the human ability to encode sequences of spatial locations. We introduce a novel paradigm in which subjects are exposed to a sequence of spatial locations on an octagon, and are asked (...) to predict future locations. The sequences vary in complexity according to a well-defined language comprising elementary primitives and recursive rules. A detailed analysis of error patterns indicates that primitives of symmetry and rotation are spontaneously detected and used by adults, preschoolers, and adult members of an indigene group in the Amazon, the Munduruku, who have a restricted numerical and geometrical lexicon and limited access to schooling. Furthermore, subjects readily combine these geometrical primitives into hierarchically organized expressions. By evaluating a large set of such combinations, we obtained a first view of the language needed to account for the representation of visuospatial sequences in humans, and conclude that they encode visuospatial sequences by minimizing the complexity of the structured expressions that capture them. (shrink)

This paper sums up the fundamental features of intelligence through the common features stated by various definitions of "intelligence": Intelligence is the ability of achieving systematic goals (functions) of brain and nerve system through selecting, and artificial intelligence or machine intelligence is an imitation of life intelligence or a replication of features and functions. Based on the definition mentioned above, this paper discusses and summarizes the development routes of ideas on computable intelligence, including Godel's "universal recursive function", (...) the computation activities of "selection", recursive function and Turing machine, mathematical expression of computable intelligence, core nature of computable intelligence, and computability and strong artificial intelligence. At the end of this paper is the conclusion drawn by the authors. (shrink)

Corcoran’s 27 entries in the 1999 second edition of Robert Audi’s Cambridge Dictionary of Philosophy [Cambridge: Cambridge UP]. -/- ancestral, axiomatic method, borderline case, categoricity, Church (Alonzo), conditional, convention T, converse (outer and inner), corresponding conditional, degenerate case, domain, De Morgan, ellipsis, laws of thought, limiting case, logical form, logical subject, material adequacy, mathematical analysis, omega, proof by recursion, recursive function theory, scheme, scope, Tarski (Alfred), tautology, universe of discourse. -/- The entire work is available online free at more (...) than one website. Paste the whole URL. http://archive.org/stream/RobertiAudi_The.Cambridge.Dictionary.of.Philosophy/Robert.Audi_The.Cambrid ge.Dictionary.of.Philosophy -/- The 2015 third edition will be available soon. Before you think of buying it read some reviews on Amazon and read reviews of its competition: For example, my review of the 2008 Oxford Companion to Philosophy, History and Philosophy of Logic,29:3,291-292. URL: http://dx.doi.org/10.1080/01445340701300429 -/- Some of the entries have already been found to be flawed. For example, Tarski’s expression ‘materially adequate’ was misinterpreted in at least one article and it was misused in another where ‘materially correct’ should have been used. The discussion provides an opportunity to bring more flaws to light. -/- Acknowledgements: Each of these entries was presented at meetings of The Buffalo Logic Dictionary Project sponsored by The Buffalo Logic Colloquium. The members of the colloquium read drafts before the meetings and were generous with corrections, objections, and suggestions. Usually one 90-minute meeting was devoted to one entry although in some cases, for example, “axiomatic method”, took more than one meeting. Moreover, about half of the entries are rewrites of similarly named entries in the 1995 first edition. Besides the help received from people in Buffalo, help from elsewhere was received by email. We gratefully acknowledge the following: José Miguel Sagüillo, John Zeis, Stewart Shapiro, Davis Plache, Joseph Ernst, Richard Hull, Concha Martinez, Laura Arcila, James Gasser, Barry Smith, Randall Dipert, Stanley Ziewacz, Gerald Rising, Leonard Jacuzzo, George Boger, William Demopolous, David Hitchcock, John Dawson, Daniel Halpern, William Lawvere, John Kearns, Ky Herreid, Nicolas Goodman, William Parry, Charles Lambros, Harvey Friedman, George Weaver, Hughes Leblanc, James Munz, Herbert Bohnert, Robert Tragesser, David Levin, Sriram Nambiar, and others. -/- . (shrink)

In the 1920s, David Hilbert proposed a research program with the aim of providing mathematics with a secure foundation. This was to be accomplished by first formalizing logic and mathematics in their entirety, and then showing---using only so-called finitistic principles---that these formalizations are free of contradictions. ;In the area of logic, the Hilbert school accomplished major advances both in introducing new systems of logic, and in developing central metalogical notions, such as completeness and decidability. The analysis of unpublished material presented (...) in Chapter 2 shows that a completeness proof for propositional logic was found by Hilbert and his assistant Paul Bernays already in 1917--18, and that Bernays's contribution was much greater than is commonly acknowledged. Aside from logic, the main technical contribution of Hilbert's Program are the development of formal mathematical theories and proof-theoretical investigations thereof, in particular, consistency proofs. In this respect Wilhelm Ackermann's 1924 dissertation is a milestone both in the development of the Program and in proof theory in general. Ackermann gives a consistency proof for a second-order version of primitive recursive arithmetic which, surprisingly, explicitly uses a finitistic version of transfinite induction up to www . He also gave a faulty consistency proof for a system of second-order arithmetic based on Hilbert's &egr;-substitution method. Detailed analyses of both proofs in Chapter 3 shed light on the development of finitism and proof theory in the 1920s as practiced in Hilbert's school. ;In a series of papers, Charles Parsons has attempted to map out a notion of mathematical intuition which he also brings to bear on Hilbert's finitism. According to him, mathematical intuition fails to be able to underwrite the kind of intuitive knowledge Hilbert thought was attainable by the finitist. It is argued in Chapter 4 that the extent of finitistic knowledge which intuition can provide is broader than Parsons supposes. According to another influential analysis of finitism due to W. W. Tait, finitist reasoning coincides with primitive recursive reasoning. The acceptance of non-primitive recursive methods in Ackermann's dissertation presented in Chapter 3, together with additional textual evidence presented in Chapter 4, shows that this identification is untenable as far as Hilbert's conception of finitism is concerned. Tait's conception, however, differs from Hilbert's in important respects, yet it is also open to criticisms leading to the conclusion that finitism encompasses more than just primitive recursive reasoning. (shrink)

-/- A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. -/- Kalish-Montague proposed using vbtos to formalize definite descriptions, set abstracts {x: F}, minimalization in recursive function theory, etc. However, they gave no sematics for vbtos. Hatcher gave a semantics but one that has flaws. We give a (...) correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture was later proved independently by the authors and by Newton da Costa. -/- The expression (vy:F) is called a variable bound term (vbt). In case F has only y free, (vy:F) has the syntactic propreties of an individual constant; and under a suitable interpretation of the language vy:F) denotes an individual. By a semantic analysis of vbtos we mean a proposal for amending the standard notions of (1) "an interpretation o f a first -order language" and (2) " the denotation of a term under an interpretation and an assignment", such that (1') an interpretation o f a first -order language associates a set-theoretic structure with each vbto and (2') under any interpretation and assignment each vb t denotes an individual. (shrink)

We describe a software system for the analysis of defined benefit actuarial plans. The system uses a recursive formulation of the actuarial stochastic processes to implement precise and efficient computations of individual and group cash flows.

Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic Analysis of (...) Variable Binding Term Operators” (Co-author John Herring), Logique et Analyse 55, 646–57. MR0307874 (46 #6989). A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. Kalish-Montague 1964 proposed using vbtos to formalize definite descriptions “the x: x+x=2”, set abstracts {x: F}, minimization in recursive function theory “the least x: x+x>2”, etc. However, they gave no semantics for vbtos. Hatcher 1968 gave a semantics but one that has flaws described in the 1971 paper and admitted by Hatcher. In 1971 we give a correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture, proved in this paper with Hatcher’s help, was proved independently about the same time by Newton da Costa. (shrink)

Although Kurt Gödel does not figure prominently in the history of computabilty theory, he exerted a significant influence on some of the founders of the field, both through his published work and through personal interaction. In particular, Gödel’s 1931 paper on incompleteness and the methods developed therein were important for the early development of recursive function theory and the lambda calculus at the hands of Church, Kleene, and Rosser. Church and his students studied Gödel 1931, and Gödel taught a (...) seminar at Princeton in 1934. Seen in the historical context, Gödel was an important catalyst for the emergence of computability theory in the mid 1930s. (shrink)

Why are natural theories pre-well-ordered by consistency strength? In previous work, an approach to this question was proposed. This approach was inspired by Martin's Conjecture, one of the most prominent conjectures in recursion theory. Fixing a reasonable subsystem $T$ of arithmetic, the goal was to classify the recursive functions that are monotone with respect to the Lindenbaum algebra of $T$. According to an optimistic conjecture, roughly, every such function must be equivalent to an iterate $\mathsf{Con}_T^\alpha$ of the consistency (...) operator ``in the limit'' within the ultrafilter of sentences that are true in the standard model. In previous work the author established the first case of this optimistic conjecture; roughly, every recursive monotone function is either as weak as the identity operator in the limit or as strong as $\mathsf{Con}_T$ in the limit. Yet in this note we prove that this optimistic conjecture fails already at the next step; there are recursive monotone functions that are neither as weak as $\mathsf{Con}_T$ in the limit nor as strong as $\mathsf{Con}_T^2$ in the limit. In fact, for every $\alpha$, we produce a function that is cofinally equivalent to $\mathsf{Con}^\alpha_T$ yet cofinally equivalent to $\mathsf{Con}_T$. (shrink)

This is a non-technical version of "The Decision Problem for Effective Procedures." The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the (...) notion of an effective procedure--without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis--that the class of effective procedures is undecidable, i.e., that no effective procedure is possible for ascertaining whether a given procedure is effective. The proof does not appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though this undecidability result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict. (shrink)

The Russell–Tarski hierarchical approach regards self-reference as a unified source of the emergence for a broad family of various semantic paradoxes. The Russell–Tarski hierarchical approach became the object of numerous critical attacks after the appearance of infinite forms of paradoxes without self-reference at the end of the 20th century. The “Infinite Liar” proposed by the American logician Stephen Yablo, in particular, is usually seen as the most powerful and convincing counterargument against the Russell–Tarski hierarchical approach. The “Infinite Liar” does not (...) contain selfreference. Each of the sentences of this infinite sequence does not speak of itself, but always only of all the following sentences, and the logical construction of this paradox is obviously isomorphic to the hierarchical structure as such. However, the truth-values of individual sentences in the “Infinite Liar” are based on recursive functions. The “Infinite Liar” by Yablo provides analytical possibilities for constructing the original computational semantics that excludes any kind of recursion in determining the truth-value, and it demonstrates effectiveness of the basic principles of the Russell–Tarski hierarchical approach in the struggle against new forms of semantic paradoxes. The “Infinite Liar” sentences are transformed into a modified computational algorithm for the Post machine. The analysis shows that for any initial state of the tape and the starting position of the cell marking mechanism, the “Infinite Liar” algorithm is quite feasible for the Post machine. The absence of a Post machine nonresultative stop in performing the “Infinite Liar” is explained by the fact that the computational algorithm of such a program has the form of a monotonous hierarchical structure in which every arbitrary sentence Sn of an infinite sequence fixes the meaning of strictly following sentences Sn+1, Sn+2, . . ., Sn+m, which completely excludes any form of recursive definitions. The disappearance of monotony in the hierarchical structure of the so-called “Dietary Infinite Liar” almost instantly leads to a nonresultative stop of the Post machine at any initial state of the tape and the starting position of the cell marking mechanism. The difference in performing demonstrated by the Post machine when executing the programs of the “Infinite Liar” and the “Dietary Infinite Liar” is a clear evidence of the effectiveness of the basic principles of the Russell–Tarski hierarchical approach in the struggle against new forms of semantic paradoxes. That is why the ban of sentences (or their sequences) with self-reference remains the most popular of standard ways in the struggle against semantic paradoxes. (shrink)

In Zettel, Wittgenstein considered a modified version of Cantor’s diagonal argument. According to Wittgenstein, Cantor’s number, different with other numbers, is defined based on a countable set. If Cantor’s number belongs to the countable set, the definition of Cantor’s number become incomplete. Therefore, Cantor’s number is not a number at all in this context. We can see some examples in the form of recursive functions. The definition "f(a)=f(a)" can not decide anything about the value of f(a). The definiton (...) is incomplete. The definition of "f(a)=1+f(a)" can not decide anything about the value of f(a) too. The definiton is incomplete.<br><br>According to Wittgenstein, the contradiction, in Cantor's proof, originates from the hidden presumption that the definition of Cantor’s number is complete. The contradiction shows that the definition of Cantor’s number is incomplete. <br><br>According to Wittgenstein’s analysis, Cantor’s diagonal argument is invalid. But different with Intuitionistic analysis, Wittgenstein did not reject other parts of classical mathematics. Wittgenstein did not reject definitions using self-reference, but showed that this kind of definitions is incomplete.<br><br>Based on Thomson’s diagonal lemma, there is a close relation between a majority of paradoxes and Cantor’s diagonal argument. Therefore, Wittgenstein’s analysis on Cantor’s diagonal argument can be applied to provide a unified solution to paradoxes. (shrink)

Complexity is a relatively new field of study that is still heavily influenced by philosophy. However, with the advent of modern computing, it has become easier to conduct thorough investigations of complex systems using computational simulations. Despite significant progress, there remain certain characteristics of complex systems that are difficult to comprehend. To better understand these features, information can be applied using simple models of complex systems. The concepts of Shannon's information theory, Kolgomorov complexity, and logical depth are helpful in this (...) regard. Computational mathematical models based on recursive processes, recursive functions, and information in functions offer new insights into complexity by exploring its connection with irreversibility and the loss of information. Through these models, it is possible to see complexity as a transformation of input information through algorithmic computation, with time, logical depth, and information loss serving as key factors in understanding the process. (shrink)

The Turing machine halting problem can be explained by several factors, including arithmetic logic irreversibility and memory erasure, which contribute to computational uncertainty due to information loss during computation. Essentially, this means that an algorithm can only preserve information about an input, rather than generate new information. This uncertainty arises from characteristics such as arithmetic logical irreversibility, Landauer's principle, and memory erasure, which ultimately lead to a loss of information and an increase in entropy. To measure this uncertainty and loss (...) of information, the concept of arithmetic logical entropy can be used. The Turing machine and its equivalent, general recursive functions can be understood through the λ calculus and the Turing/Church thesis. However, there are certain recursive functions that cannot be fully understood or predicted by other algorithms due to the loss of information during logical-arithmetic operations. In other words, the behaviour of these functions cannot be completely determined at every stage of the computation due to a lack of information in their definition. While there are some cases where the behaviour of recursive functions is highly predictable, the lack of information in most cases makes it impossible for algorithms to determine if a program will halt or not. This inability to predict the outcome of the computation is the essence of the halting problem of the Turing machine. Even in cases where more information is available about the program, it is still difficult to determine with certainty if the program will halt or not. This also highlights the importance of the Turing oracle machine, which introduces information from outside the computation to compensate for the lack of information and ultimately decide the result of the computation. (shrink)

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, (...) in: R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

We model infinite regress structures -not arguments- by means of ungrounded recursively defined functions in order to show that no such structure can perform the task of providing determination to the items composing it, that is, that no determination process containing an infinite regress structure is successful.

In the first part of the paper I argue that an ontology of events is precise, flexible and general enough so as to cover the three main alternative formulations of quantum mechanics as well as theories advocating an antirealistic view of the wave function. Since these formulations advocate a primitive ontology of entities living in four-dimensional spacetime, they are good candidates to connect that quantum image with the manifest image of the world. However, to the extent that some form (...) of realism about the wave function is also necessary, one needs to endorse also the idea that the wave function refers to some kind of power. In the second part, I discuss some difficulties raised by the recent proposal that in Bohmian mechanics this power is holistically possessed by all the particles in the universe. (shrink)

The abstract basis of modern computation is the formal description of a finite state machine, the Universal Turing Machine, based on manipulation of integers and logic symbols. In this contribution to the discourse on the computer-brain analogy, we discuss the extent to which analog computing, as performed by the mammalian brain, is like and unlike the digital computing of Universal Turing Machines. We begin with ordinary reality being a permanent dialog between continuous and discontinuous worlds. So it is with computing, (...) which can be analog or digital, and is often mixed. The theory behind computers is essentially digital, but efficient simulations of phenomena can be performed by analog devices; indeed, any physical calculation requires implementation in the physical world and is therefore analog to some extent, despite being based on abstract logic and arithmetic. The mammalian brain, comprised of neuronal networks, functions as an analog device and has given rise to artificial neural networks that are implemented as digital algorithms but function as analog models would. Analog constructs compute with the implementation of a variety of feedback and feedforward loops. In contrast, digital algorithms allow the implementation of recursive processes that enable them to generate unparalleled emergent properties. We briefly illustrate how the cortical organization of neurons can integrate signals and make predictions analogically. While we conclude that brains are not digital computers, we speculate on the recent implementation of human writing in the brain as a possible digital path that slowly evolves the brain into a genuine (slow) Turing machine. (shrink)

Lam and Esfeld have argued that, within Bohmian mechanics, the wave function can be interpreted as a physical structure instantiated by the fundamental particles posited by the theory. Further, to characterize the nature of this structure, they appeal to the framework of Ontic Structural Realism, thereby proposing a structuralist interpretation of Bohmian mechanics. However, I shall point out that OSR denotes a family of distinct views, each of which maintains a different account about the relation between structures and objects, and (...) entails a different kind of ontology. Thus, in this paper I will show how to articulate the structuralist approach to Bohmian Mechanics accordingly to the different standard versions of OSR, and I will evaluate these alternatives. Moreover, I will propose a novel and _sui generis_ kind of structuralist interpretation of Bohmian Mechanics, based on the framework of metaphysical coherentism. (shrink)

I show that there are good arguments and evidence to boot that support the language as an instrument of thought hypothesis. The underlying mechanisms of language, comprising of expressions structured hierarchically and recursively, provide a perspective (in the form of a conceptual structure) on the world, for it is only via language that certain perspectives are avail- able to us and to our thought processes. These mechanisms provide us with a uniquely human way of thinking and talking about the world (...) that is different to the sort of thinking we share with other animals. If the primary function of language were communication then one would expect that the underlying mechanisms of language will be structured in a way that favours successful communication. I show that not only is this not the case, but that the underlying mechanisms of language are in fact structured in a way to maximise computational efficiency, even if it means causing communicative problems. Moreover, I discuss evidence from comparative, neuropatho- logical, developmental, and neuroscientific evidence that supports the claim that language is an instrument of thought. (shrink)

The paper shows how the Bohmian approach to quantum physics can be applied to develop a clear and coherent ontology of non-perturbative quantum gravity. We suggest retaining discrete objects as the primitive ontology also when it comes to a quantum theory of space-time and therefore focus on loop quantum gravity. We conceive atoms of space, represented in terms of nodes linked by edges in a graph, as the primitive ontology of the theory and show how a non-local law (...) in which a universal and stationary wave-function figures can provide an order of configurations of such atoms of space such that the classical space-time of general relativity is approximated. Although there is as yet no fully worked out physical theory of quantum gravity, we regard the Bohmian approach as setting up a standard that proposals for a serious ontology in this field should meet and as opening up a route for fruitful physical and mathematical investigations. (shrink)

This paper is a brief (and hopelessly incomplete) non-standard introduction to the philosophy of space and time. It is an introduction because I plan to give an overview of what I consider some of the main questions about space and time: Is space a substance over and above matter? How many dimensions does it have? Is space-time fundamental or emergent? Does time have a direction? Does time even exist? Nonetheless, this introduction is not standard because I conclude the discussion by (...) presenting the material with an original spin, guided by a particular understanding of fundamental physical theories, the so-called primitive ontology approach. (shrink)

This article presents a formal ontology which accounts for the general nature of artefacts. The objective is to help structure application ontologies in areas where specific artefacts are present - in other words, virtually any area of activity. The conceptualization relies on recent philosophical and psychological research on artefacts, having resulted in a largely consensual theoretical basis. Furthermore, this ontology of artefacts extends the foundational DOLCE ontology and supplements its axiomatization. The conceptual primitives are as follows: artificial entity, intentional production (...) of entities, (state of) capacity, capacity to play a role in actions of a given type, function and functional object. These primitives enable artefacts in general to be characterized as intentionally and successfully produced entities, and isolate an important subclass of “technical” artefacts to which a function is ascribed. Lastly, we emphasize the novelty of this ontology by comparing it with other works with similar objectives. (shrink)

Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. Let R be a subring of Q with or without 1. By H_{10}(R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide (...) whether or not the equation has a solution in R. We prove that a positive solution to H_{10}(R) implies that the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable. We show the converse implication for every infinite set R \subseteq Q such that there exist computable functions \tau_1,\tau_2:N \to Z which satisfy (\forall n \in N \tau_2(n) \neq 0) \wedge ({\frac{\tau_1(n)}{\tau_2(n)}: n \in N}=R). This implication for R=N guarantees that Smoryński's theorem follows from Matiyasevich's theorem. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have a rational solution is not recursive. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have only finitely many rational solutions is not recursively enumerable. These conjectures are equivalent by our results for R=Q. (shrink)

The paper points out that the modern formulation of Bohm’s quantum theory known as Bohmian mechanics is committed only to particles’ positions and a law of motion. We explain how this view can avoid the open questions that the traditional view faces according to which Bohm’s theory is committed to a wave-function that is a physical entity over and above the particles, although it is defined on configuration space instead of three-dimensional space. We then enquire into the status of the (...) law of motion, elaborating on how the main philosophical options to ground a law of motion, namely Humeanism and dispositionalism, can be applied to Bohmian mechanics. In conclusion, we sketch out how these options apply to primitive ontology approaches to quantum mechanics in general. (shrink)

Frames, i.e., recursive attribute-value structures, are a general format for the decomposition of lexical concepts. Attributes assign unique values to objects and thus describe functional relations. Concepts can be classified into four groups: sortal, individual, relational and functional concepts. The classification is reflected by different grammatical roles of the corresponding nouns. The paper aims at a cognitively adequate decomposition, particularly, of sortal concepts by means of frames. Using typed feature structures, an explicit formalism for the characterization of cognitive frames (...) is developed. The frame model can be extended to account for typicality effects. Applying the paradigm of object-related neural synchronization, furthermore, a biologically motivated model for the cortical implementation of frames is developed. Cortically distributed synchronization patterns may be regarded as the fingerprints of concepts. (shrink)

This paper articulates and defends a conception of logical form as semantic form revealed by a compositional meaning theory. On this conception, the logical form of a sentence is determined by the semantic types of its primitive terms and their mode of combination as it relates to determining under what conditions it is true. We develop this idea in the framework of truth-theoretic semantics. We argue that the semantic form of a declarative sentence in a language L is revealed (...) by a (canonical) proof of its T- sentence in an interpretive truth theory for L. We give a precise characterization of sameness of logical form between any two declarative sentences in any two languages in terms of the notion of corresponding proofs in interpretive truth theories for the languages. We illustrate the utility of this approach with a number of examples. We then extend the characterization to non-declaratives in a generalization of truth-theoretic semantics that appeals to fulfillment conditions, of which truth conditions are one variety. On this approach, logical forms are not reified, and the notion of sameness of logical form is treated as conceptually basic. We discuss the relation of this conception of logical form to the project of identifying logical constants, reviewing two approaches, one of which takes topic neutrality as central, the other recursion. We argue that the project of identifying logical constants for the purposes of classifying together valid arguments is largely independent of that identifying logical form of sentences, and urge an ecumenical approach to extending talk of logical constants beyond where it is currently well-grounded. (shrink)

ABSTRACT According to edenic idealism, our ordinary object terms refer to items in the manifest world—the world of primitive objects and properties presented in experience. I motivate edenic idealism as a response to scenarios where it is difficult to match the objects in experience with corresponding items in the external world. I argue that edenic idealism has important semantic advantages over realism: it is the most intuitive view of what we are actually talking about when we use terms for (...) objects. (shrink)

A number of philosophers and logicians have argued for the conclusion that maps are logically tractable modes of representation by analyzing them in propositional terms. But in doing so, they have often left what they mean by "propositional" undefined or unjustified. I argue that propositions are characterized by a structure that is digital, universal, asymmetrical, and recursive. There is little positive evidence that maps exhibit these features. Instead, we can better explain their functional structure by taking seriously the observation (...) that maps arrange their constituent elements in a non-hierarchical, holistic structure. This is compatible with the more basic claim advanced by defenders of a propositional analysis: that (many) maps do have formal semantics and logic. (shrink)

One theoretical charge (of Optimality Theory in its early conception) must have been to retain that sense of qualitative particularity as affecting as constraining theory relevant to a proscribed field when clearly a motivation was to divine in circumscriptions operational consequences conceived on a deferred abstractive level. An attraction of the theory's embodying results of constraint interactions as responsive to theory-internal qualitative implementation, as being in fact supplementarily transparent to co-ordinations of variously language specific implementations, qualitative identifications, was apparent naturalistic (...) coordination of defined features taken here—in OT—at one fell-swoop. Differently put, the uses of analyses of the relevant types of spaces (‘primitive from the viewpoint of linguistic theories’) will (latterly) involve a period of time-stretch or compression over a previously normal (I take it) process of embeddings in a new theorised and recursively enacted invocation/re-invocation of base as digestively present in results of corrected theories. Or as Prince and Smolensky have it -/- 'What we have done, in essence, is to replace the iterative procedure (act/evaluate, act/evaluate, . . . ) with a recursive scheme: collect the results of all possible actions, then sort recursively.' OT, 16. (shrink)