The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that (...) non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind. (shrink)

This book is dedicated to a classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting the basic ideas of whole number, function, proof, and real number. Part II starts with readings from Turing and Post leading to the formal theory of recursive functions. Part III presents (...) sufficient formal logic to give a full development of Gödel's incompleteness theorems. Part IV considers the significance of the technical work with a discussion of Church's Thesis and readings on the foundations of mathematics. This new edition contains the timeline "Computability and Undecidability" as well as the essay "On mathematics". (shrink)

Turing and Church formulated two different formal accounts of computability that turned out to be extensionally equivalent. Since the accounts refer to different properties they cannot both be adequate conceptual analyses of the concept of computability. This insight has led to a discussion concerning which account is adequate. Some authors have suggested that this philosophical debate—which shows few signs of converging on one view—can be circumvented by regarding Church’s and Turing’s theses as explications. This move opens up the possibility that (...) both accounts could be adequate, albeit in their own different ways. In this paper, I focus on the question of whether Church’s thesis can be seen as an explication in the precise Carnapian sense. Most importantly, I address an additional constraint that Carnap puts on the explicative power of axiomatic systems—an axiomatisation explicates when it is clear which mathematical entities form the theory’s intended model—and that implicitly applies to axiomatisations of recursion theory used in Church’s account of computability. To overcome this difficulty, I propose two possible clarifications of the pre-systematic concept of “computability” that can both be captured in recursion theory, and I show how both clarifications avoid an objection arising from Carnap’s constraint. (shrink)

For a general formulation of the undecidability and incompleteness theorems one has to characterize precisely the notion of formal system. Such a characterization is provided by the proposal to identify the intuitive concept of effectively calculable function with that of partial recursive function. A proper understanding of this identification, which is known under the name of "Church's thesis", is crucial for a philosophical assessment of these metamathematical results. The undecidability and incompleteness theorems suggest one major but certainly not the (...) only reason for interest in Church's thesis. The thesis provides a sharp characterization of a concept that has played an epistemologically motivated role in many logical and foundational investigations and that has been appealed to in methodological discussions concerning computational approaches in cognitive psychology. ;In spite of these various motives of interest a detailed philosophical analysis of the meaning and the epistemological status of Church's thesis has been neglected; a thorough and balanced presentation of arguments for it is lacking. This seems to me to be due to two widespread views of the thesis, both tending to discourage analytical work. According to the first of these views, Church's thesis is unproblematic because the classical arguments for the identification are convincing. According to the second view, it is hopeless to try to evaluate the adequacy of a proposed mathematical characterization of effectiveness, because the intuitive notion is too vague. The analysis undertaken in this thesis conflicts with both views. ;I All classical arguments for Church's thesis, including Turing's, have unconvincing aspects. ;II Some generalizations of Turing's work show that unconvincing aspects of Turing's argument can be dispensed with and provide conceptually significant contributions to the problem of a "natural" mathematical characterization of the mechanically calculable functions. ;III One can isolate meanings of effectiveness conceptually more inclusive than mechanical calculability and distinguish between corresponding interpretations of Church's thesis. ;The analytical work supporting these claims bears significantly on the philosophical issues mentioned above: it plays a crucial role in a philosophical evaluation of the undecidability and incompleteness theorems and in a clarification of the conceptual background of computational approaches in cognitive psychology. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers (...) by Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof (...) of Church's Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

Between inventing the concept of a universal computer in 1936 and breaking the German Enigma code during World War II, Alan Turing, the British founder of computer science and artificial intelligence, came to Princeton University to study mathematical logic. Some of the greatest logicians in the world--including Alonzo Church, Kurt Gödel, John von Neumann, and Stephen Kleene--were at Princeton in the 1930s, and they were working on ideas that would lay the groundwork for what would become known as computer science. (...) Though less well known than his other work, Turing's 1938 Princeton PhD thesis, "Systems of Logic Based on Ordinals," which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics. This book presents a facsimile of the original typescript of the thesis along with essays by Andrew Appel and Solomon Feferman that explain its still-unfolding significance. A work of philosophy as well as mathematics, Turing's thesis envisions a practical goal--a logical system to formalize mathematical proofs so they can be checked mechanically. If every step of a theorem could be verified mechanically, the burden on intuition would be limited to the axioms. Turing's point, as Appel writes, is that "mathematical reasoning can be done, and should be done, in mechanizable formal logic." Turing's vision of "constructive systems of logic for practical use" has become reality: in the twenty-first century, automated "formal methods" are now routine. Presented here in its original form, this fascinating thesis is one of the key documents in the history of mathematics and computer science. (shrink)

This paper concerns Alan Turing’s ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for (...) Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the “mathematical
objection” to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it
should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human
mathematicians presumably do. (shrink)

The recent development of the research field of Computing and Philosophy has triggered investigations into the theoretical foundations of computing and information. This thesis consists of two parts which are the result of studies in two areas of Philosophy of Computing and Philosophy of Information regarding the production of meaning and the value system with applications. The first part develops a unified dual-aspect theory of information and computation, in which information is characterized as structure, and computation is the information (...) dynamics. This enables naturalization of epistemology, based on interactive information representation and communication. In the study of systems modeling, meaning, truth and agency are discussed within the framework of the PI/PC unification. The second part of the thesis addresses the necessity of ethical judgment in rational agency illustrated by the problem of information privacy and surveillance in the networked society. The value grounds and socio-technological solutions for securing trustworthiness of computing are analyzed. Privacy issues clearly show the need for computing professionals to contribute to understanding of the technological mechanisms of Information and Communication Technology. The main original contribution of this thesis is the unified dual-aspect theory of computation/information. Semantics of information is seen as a part of the data-information-knowledge structuring, in which complex structures are self-organized by the computational processing of information. Within the unified model, complexity is a result of computational processes on informational structures. The thesis argues for the necessity of computing beyond the Turing-Church limit, motivated by natural computation, and wider by pancomputationalism and paninformationalism, seen as two complementary views of the same physical reality. Moreover, it follows that pancomputationalism does not depend on the assumption that the physical world on some basic level is digital. Contrary to many believes it is entirely compatible with dual quantum-mechanical computing. (shrink)

Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turing machines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, (...) we must correlate these syntactic entities with numbers. I argue that, in providing this correlation, we must demand that the correlation itself be computable. Otherwise, the Turing machine will compute uncomputable functions. But if we presuppose the intuitive notion of a computable relation between syntactic entities and numbers, then our analysis of computability is circular. (shrink)

Church's and Turing's theses dogmatically assert that an informal notion of effective calculability is adequately captured by a particular mathematical concept of computability. I present an analysis of calculability that is embedded in a rich historical and philosophical context, leads to precise concepts, but dispenses with theses. To investigate effective calculability is to analyze symbolic processes that can in principle be carried out by calculators. This is a philosophical lesson we owe to Turing. Drawing on that lesson and (...) recasting work of Gandy, I formulate boundedness and locality conditions for two types of calculators, namely, human computing agents and mechanical computing devices (discrete machines). The distinctive feature of the latter is that they can carry out parallel computations. The analysis leads to axioms for discrete dynamical systems (representing human and machine computations) and allows the reduction of models of these axioms to Turing machines. Cellular automata and a variety of artificial neural nets can be shown to satisfy the axioms for machine computations. (shrink)

A. M. Turing has bequeathed us a conceptulary including 'Turing, or Turing-Church, thesis', 'Turing machine', 'universal Turing machine', 'Turing test' and 'Turing structures', plus other unnamed achievements. These include a proof that any formal language adequate to express arithmetic contains undecidable formulas, as well as achievements in computer science, artificial intelligence, mathematics, biology, and cognitive science. Here it is argued that these achievements hang together and have prospered well in the 50 years since Turing's death.

We aim at providing a philosophical analysis of the notion of “proof by Church’s Thesis”, which is – in a nutshell – the conceptual device that permits to rely on informal methods when working in Computability Theory. This notion allows, in most cases, to not specify the background model of computation in which a given algorithm – or a construction – is framed. In pursuing such analysis, we carefully reconstruct the development of this notion (from Post to Rogers, to (...) the present days), and we focus on some classical constructions of the field, such as the construction of a simple set. Then, we make use of this focus in order to support the following encompassing claim (which opposes to a somehow commonly received view): the informal side of Computability, consisting of the large class of methods typically employed in the proofs of the field, is not fully reducible to its formal counterpart. (shrink)

Church's thesis, that all reasonable definitions of “computability” are equivalent, is not usually thought of in terms of computability by acontinuouscomputer, of which the general-purpose analog computer (GPAC) is a prototype. Here we prove, under a hypothesis of determinism, that the analytic outputs of aC∞GPAC are computable by a digital computer.In [POE, Theorems 5, 6, 7, and 8], Pour-El obtained some related results. (The proof there of Theorem 7 depends on her Theorem 2, for which the proof in (...) [POE] is incorrect, but for which a correct proof is given in [LIR]. Also, the proof in [POE] of Theorem 8 depends on the unproved assertion that a solution of an algebraic differential equation must be analytic on an open subset of its domain. However, this assertion was later proved in [BRR].) As in [POE], we reduce the problem to a problem about solutions of certain systems of algebraic differential equations (ADE's). If such a system is nonsingular (i.e. if the “separant” does not vanish along the given solution), then the argument is very easy (see [VSD] for an even simpler situation), so that the essential difficulties arise fromsingularsystems. Our main tools in handling these difficulties are drawn from the excellent (and difficult) paper [DEL] by Denef and Lipshitz. The author especially wants to thank Leonard Lipshitz for his kind help in the preparation of the present paper.We emphasize here that our proof of the simulation result applies only to the GPAC as described below. The GPAC's form a natural subclass of the class of all analog computers, and are based on certain idealized components (“black boxes”), mostly associated with the technology of past decades. One can easily envisage other kinds of black boxes of an input-output character that would lead to different kinds of analog computers. (For example, one could incorporate delays, or spatial integrators in addition to the present temporal integrators, etc.) Whether digital simulation is possible for these “extended” analog computers poses a rich and challenging set of research questions. (shrink)

The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of (...) what constitutes a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is.The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular ifPis some property, then the statement “for eachmthere isnsuch thatP” means that we can construct a functionθsuch thatP)for allm. Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive.One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions. (shrink)

Though less well known than his other work, Turings 1938 Princeton Thesis, this title which includes his notion of an oracle machine, has had a lasting influence on computer science and mathematics. It presents a facsimile of the original typescript of the thesis along with essays by Appel and Feferman that explain its still-unfolding significance.

It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined (...) with Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. (shrink)

Following Post program, we will propose a linguistic and empirical interpretation of Gödel’s incompleteness theorem and related ones on unsolvability by Church and Turing. All these theorems use the diagonal argument by Cantor in order to find limitations in finitary systems, as human language, which can make “infinite use of finite means”. The linguistic version of the incompleteness theorem says that every Turing complete language is Gödel incomplete. We conclude that the incompleteness and unsolvability theorems find limitations in (...) our finitary tool, which is our complete language. (shrink)

This work addresses a broad range of questions which belong to four fields: computation theory, general philosophy of science, philosophy of cognitive science, and philosophy of mind. Dynamical system theory provides the framework for a unified treatment of these questions. ;The main goal of this dissertation is to propose a new view of the aims and methods of cognitive science--the dynamical approach . According to this view, the object of cognitive science is a particular set of dynamical (...) systems, which I call "cognitive systems". The goal of a cognitive study is to specify a dynamical model of a cognitive system, and then use this model to produce a detailed account of the specific cognitive abilities of that system. The dynamical approach does not limit a-priori the form of the dynamical models which cognitive science may consider. In particular, this approach is compatible with both computational and connectionist modeling, for both computational systems and connectionist networks are special types of dynamical systems. ;To substantiate these methodological claims about cognitive science, I deal first with two questions in two different fields: What is a computational system? What is a dynamical explanation of a deterministic process? ;Intuitively, a computational system is a deterministic system which evolves in discrete time steps, and which can be described in an effective way. In chapter 1, I give a formal definition of this concept which employs the notions of isomorphism between dynamical systems, and of Turing computable function. In chapter 2, I propose a more comprehensive analysis which is based on a natural generalization of the concept of Turing machine. ;The goal of chapter 3 is to develop a theory of the dynamical explanation of a deterministic process. By a "dynamical explanation" I mean the specification of a dynamical model of the system or process which we want to explain. I start from the analysis of a specific type of explanandum--dynamical phenomena--and I then use this analysis to shed light on the general form of a dynamical explanation. Finally, I analyze the structure of those theories which generate explanations of this form, namely dynamical theories. (shrink)

Which function is computed by a Turing machine will depend on how the symbols it manipulates are interpreted. Further, by invoking bizarre systems of notation it is easy to define Turing machines that compute textbook examples of uncomputable functions, such as the solution to the decision problem for first-order logic. Thus, the distinction between computable and uncomputable functions depends on the system of notation used. This raises the question: which systems of notation are the relevant ones for (...) determining whether a function is computable? These are the acceptable notations. I argue for a use criterion of acceptability: the acceptable notations for a domain of objects D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document} are the notations that we can use for the usual D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document}-activities. Acceptable notations for natural numbers are ones that we can count with. Acceptable notations for logical formulas are the ones that we can use in inference and logical analysis. And so on. This criterion makes computability a relative notion—whether a function is computable depends on which notations are acceptable, which is relative to our interests and abilities. I argue that this is not a problem, however, since there is independent reason for taking the extension of computable function to be relative to contingent facts. Similarly, the fact that the use criterion makes a mathematical distinction depend on practical concerns is also not a problem because it dovetails with similar phenomena in other areas of computability theory, namely the roles of notation in computation over real numbers and of Extended Church’s Thesis in complexity theory. (shrink)

``Neural computing'' is a research field based on perceiving the human brain as an information system. This system reads its input continuously via the different senses, encodes data into various biophysical variables such as membrane potentials or neural firing rates, stores information using different kinds of memories (e.g., short-term memory, long-term memory, associative memory), performs some operations called ``computation'', and outputs onto various channels, including motor control commands, decisions, thoughts, and feelings. We show a natural model of neural computing that (...) gives rise to hyper-computation. Rigorous mathematical analysis is applied, explicating our model's exact computational power and how it changes with the change of parameters. Our analog neural network allows for supra-Turing power while keeping track of computational constraints, and thus embeds a possible answer to the superiority of the biological intelligence within the framework of classical computer science. We further propose it as standard in the field of analog computation, functioning in a role similar to that of the universal Turing machine in digital computation. In particular an analog of the Church-Turing thesis of digital computation is stated where the neural network takes place of the Turing machine. (shrink)

The thesis of the paper is that semiotic processes are intrinsic to computation and computational systems. An explanation of computation that does not take this semiotic dimension into account is incomplete. Semiosis is essential to computation and therefore requires a rigorous definition. To prove this thesis, the author analyzes two concepts of computation: the Turing machine and the mechanistic conception of physical computation. The paper is organized in two parts. The first part (Sects. 2 and 3) develops a re-interpretation (...) of the Turing machine starting from Peirce’s semiotics. The author shows how this reinterpretation allows overcoming the dualism between a purist and a realist version of the Turing machine. The second part of the paper (Sect. 4) shows how a mechanistic explanation of physical computation such as the one developed by Piccinini is incomplete without considering semiotic relations. The paper intends to be a contribution to the philosophical debate on computation. (shrink)

Church's Thesis states the equivalence of computable functions and recursive functions. This can be interpreted as a definition, as an explanation, as an axiom, and as a proposition of mechanistic philosophy. A number of arguments and objections, including a pair of counterexamples based on Gödel's Incompleteness Theorem, allow to conclude that Church's Thesis can be reasonably taken both as a definition and as an axiom, somewhat less convincingly as an explanation, but hardly as a mechanistic proposition.

We consider processes of emergence within the conceptual framework of the Information Loss principle and the concepts of systems conserving information; systems compressing information; and systems amplifying information. We deal with the supposed incompatibility between emergence and computability tout-court. We distinguish between computational emergence, when computation acquires properties, and emergent computation, when computation emerges as a property. The focus is on emergence processes occurring within computational processes. Violations of Turing-computability such as non-explicitness and incompleteness are intended to (...) represent partially the properties of phenomenological emergence, such as logical openness, given by the observer’s cognitive role; structural dynamics where change regards rules rather than only values; and multi-modelling where multiple non-equivalent models are required to model such structural dynamics. In this way, we validate, from an epistemological viewpoint, models and simulations of phenomenological emergence where the sequence of events constitutes the natural, analogical non-Turing computation which a cognitive complex system can reproduce through learning. Reproducibility through learning is different from Turing-like computational iteration. This paper aims to open a new, non-reductionist understanding of the conceptual relationship between emergence and computability. (shrink)

This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...) propositions, and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. Elohim develops a novel, topic-sensitive truthmaker semantics for dynamic epistemic logic, and develops a novel, dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for two-dimensional (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} is availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between Elohim's hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. Elohim countenances a hyperintensional semantics for novel epistemic abstractionist modalities. Elohim suggests, too, that higher observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for two-dimensional hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. Elohim invents a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. Elohim provides a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . (...) No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. (shrink)

Church's Undecidability Theorem is one of the meta-theoretical results of the mid-third decade of the last century, which along with other limiting theorems such as those of Gödel and Tarski have generated endless reflections and analyzes, both within the framework of the formal sciences, that is, mathematics, logic and theoretical computation, as well as outside them, especially the philosophy of mathematics, philosophy of logic and philosophy of mind. We propose, as a general purpose of this article, to formulate (...) class='Hi'>Church's Undecidability Theorem and present the main ideas of its demonstration. In order to carry out the first objective, we need to introduce and explain the notions of recursive function and numbering used by Gödel, which will allow to formally and rigorously enunciate Church's Theorem. After we enunciate Church's Theorem of Unspeakability in a formal and rigorous manner, we will present the main ideas of the proof of Church's Undecidability Theorem for First Order Logic, which uses Robinson's axiomatic system for arithmetic and four facts about himself: In Robinson's system for arithmetic recursive functions are representable Robinson's system is undecidable, The number of axioms proper to the Robinson system is finite and The logical calculation of the Robinson system is equal to the calculation of the first-order logic. (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)

Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...) Turing’s analysis of computability; Turing’s Notational Thesis. (shrink)

What are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We (...) will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable. (shrink)

This book uses the friendly format of the computing language Prolog to teach a full formal predicate logic. With Prolog, the scope and limits of both logic and computing can be explored and experimented. Students learning formal logic in a Prolog format can begin using their already developed informal abilities in logic to program in Prolog and conversely learn enough formal logic to examine Prolog and computing in general so major fundamental theorems can be demonstrated. Cases such as Church's (...) Thesis, Church's Theorem, Turing's Halting Problem, and Godel's Incompleteness Theorem provide the author with the means to assess some of the philosophical implications of logic and computing. Henry designed the book for undergraduate students, but it is also useful for philosophers and theologians who wish to see how computer programming serves as a probe into philosophical matters. Contents: The Formalization of Logic; Propositional Logic; Predicate Logic; Prolog: Programming in Logic; Logic Machines; The Scope and Limits of Logic and Logic Machines; Philosophical Reflections; Appendix; Bibliography; Index. (shrink)

In his classic paper On Computable Numbers Turing analyzed what can be done by a human computor in a routine, “mechanical” way. He argued that mechanical op-erations obey locality conditions and are carried out on configurations satisfying boundedness conditions. Processes meeting these restrictive conditions can be shown to be computable by a Turing machine. Turing viewed memory limitations of computors as the ultimate reason for the restrictive conditions. In contrast, Gandy analyzed in his paper Church’s Thesis and Principles (...) for Mechanisms what can be done by “discrete deterministic mechanical devices” and appealed to physical considerations to motivate restrictive principles. These devices include, crucially, ones that carry out parallel processes, e.g., cellular automata. Following Turing’s methodological ways and guided by Conway’s “Game of Life” as a paradigm, Gandy formulated four restrictive principles and proved that devices satisfying them are computationally equivalent to Turing machines. (shrink)

The purpose of this article is to examine aspects of the development of the concept and theory of computability through the theory of recursive functions. Following a brief introduction, Section 2 is devoted to the presuppositions of computability. It focuses on certain concepts, beliefs and theorems necessary for a general property of computability to be formulated and developed into a mathematical theory. The following two sections concern situations in which the presuppositions were realized and the theory of computability was developed. (...) It is suggested in Section 3 that a central item was the problem of generalizing Gödel's incompleteness theorem. It is shown that this involved both the characterization of recursiveness and the attempt to clarify and formulate the notion of an effective process as it relates to the syntax of deductive systems. Section 4 concerns the decision problems which grew from the Hilbert program. Section 5 is devoted to the development of an informal' technique in the theory of computability often called ?argument by Church's thesis? (shrink)

In his preface, Hunter explains that this volume is intended to provide for non-mathematicians an introduction to the most important results of modern mathematical logic. The reader will find here the work of Post, Skolem, Gödel, Church, Henkin, and others, presented in a terse and closely-knit style. Though acknowledging the trend toward natural deduction systems, Hunter sticks to more classical axiomatic systems on the grounds that the proofs of metatheorems are simplified by that choice. He begins with (...) a formal system of propositional logic, for which he develops proofs of completeness, consistency, and decidability. Systems of first order predicate logic are then dealt with, and Church's and Gödel's results on undecidability and incompleteness are presented. There is a brief, useful discussion indicating what parts of first order predicate logic are decidable. It is assumed that the reader has some familiarity with elementary formal logic: Hunter develops the set-theoretical results he requires. The compactness of the presentation is facilitated by the use of earlier results for propositional logic to obtain certain results for predicate logic. Especially helpful is Hunter's technique of prefacing each of the longer and more difficult proofs with a section explaining the key ideas and the general method of proof; summaries are also often provided in conclusion. Because of the orientation of the book, a more extensive discussion of the significance of the results obtained and the philosophical issues which have been raised concerning some of them, would have been welcome. Nonetheless, this is a good, concise introduction for those who are not yet prepared to tackle the more technical literature. A bibliography is provided for those interested in pursuing the subject in greater detail.--E. M. F. (shrink)

The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective (...) procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)

We sketch the historical and conceptual context of Turing's analysis of algorithmic or mechanical computation. We then discuss two responses to that analysis, by Gödel and by Gandy, both of which raise, though in very different ways. The possibility of computation procedures that cannot be reduced to the basic procedures into which Turing decomposed computation. Along the way, we touch on some of Cleland's views.

Traditionally, many writers, following Kleene (1952), thought of the Church-Turing thesis as unprovable by its nature but having various strong arguments in its favor, including Turing’s analysis of human computation. More recently, the beauty, power, and obvious fundamental importance of this analysis, what Turing (1936) calls “argument I,” has led some writers to give an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this chapter I advocate an alternative justification, essentially presupposed by Turing (...) himself in what he calls “argument II.” The idea is that computation is a special form of mathematical deduction. Assuming the steps of the deduction can be stated in a first order language, the Church-Turing thesis follows as a special case of Gödel’s completeness theorem (first order algorithm theorem). I propose this idea as an alternative foundation for the Church-Turing thesis, both for human and machine computation. Clearly the relevant assumptions are justified for computations presently known. Other issues, such as the significance of Gödel’s 1931 Theorem IX for the Entscheidungsproblem, are discussed along the way. (shrink)

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's (...) thesis. (shrink)

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, (...) following state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.... (shrink)

What counts as a computation and how it relates to cognitive function are important questions for scientists interested in understanding how the mind thinks. This paper argues that pragmatic aspects of explanation ultimately determine how we answer those questions by examining what is needed to make rigorous the notion of computation used in the (cognitive) sciences. It (1) outlines the connection between the Church-Turing Thesis and computational theories of physical systems, (2) differentiates merely satisfying a computational function from true (...) computation, and finally (3) relates how we determine a true computation to the functional methodology in cognitive science. All of the discussion will be directed toward showing that the only way to connect formal notions of computation to empirical theory will be in virtue of the pragmatic aspects of explanation. (shrink)

Kripke (1982, Wittgenstein on rules and private language. Cambridge, MA: MIT Press) presents a rule-following paradox in terms of what we meant by our past use of “plus”, but the same paradox can be applied to any other term in natural language. Many responses to the paradox concentrate on fixing determinate meaning for “plus”, or for a small class of other natural language terms. This raises a problem: how can these particular responses be generalised to the whole of natural language? (...) In this paper, I propose a solution. I argue that if natural language is computable in a sense defined below, and the Church–Turing thesis is accepted, then this auxiliary problem can be solved. (shrink)

We first discuss Michael Dummett’s philosophy of mathematics and Robert Brandom’s philosophy of language to demonstrate that inferentialism entails the falsity of Church’s Thesis and, as a consequence, the Computational Theory of Mind. This amounts to an entirely novel critique of mechanism in the philosophy of mind, one we show to have tremendous advantages over the traditional Lucas-Penrose argument.

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...) do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 01–complete. These results go via reduction to problems concerning domino systems. (shrink)

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

Wilfried Sieg. Formal Systems, Church Turing Thesis, and Gödel's Theorems: Three Contributions to The MIT Encyclopedias of Cognitive Science.

The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. Specifically, communication with the outside world happens during the computation, not before or after it. This approach radically changes our understanding of what is computation and how it is modeled. The acceptance of interaction as a new (...) paradigm is hindered by the Strong Church–Turing Thesis (SCT), the widespread belief that Turing Machines (TMs) capture all computation, so models of computation more expressive than TMs are impossible. In this paper, we show that SCT reinterprets the original Church–Turing Thesis (CTT) in a way that Turing never intended; its commonly assumed equivalence to the original is a myth. We identify and analyze the historical reasons for the widespread belief in SCT. Only by accepting that it is false can we begin to adopt interaction as an alternative paradigm of computation. We present Persistent Turing Machines (PTMs), that extend TMs to capture sequential interaction. PTMs allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of TMs and of the CTT. The paradigm shift to interaction provides an alternative understanding of the nature of computing that better reflects the services provided by today’s computing technology. (shrink)