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)

In this paper I add credence to Linda Zagzebski's (1994) diagnosis of Gettier problems (and the current trend to abandon the standard analysis) by analyzing the nature of luck. It is widely accepted that the lesson to be learned from Gettier problems is that knowledge is incompatible with luck or at least a certain species thereof. As such, understanding the nature of luck is central to understanding the Gettier problem. Thanks by and large to Duncan Pritchard's seminal work, Epistemic Luck, (...) a great deal of literature has been developed recently concerning the nature of luck and anti-luck epistemology. The literature, however, has yet to explore the very intuitive idea that luck comes in degrees. I propose that once luck is recognized to admit degrees even the slightest non-zero degree (of the relevant sort) precludes knowledge. Connecting this to Zagzebski's thesis, I propose that a given theory of warrant must guarantee truth in order to avoid Gettier counterexamples (or subsequently deny that warrant bears any relationship to the truth whatsoever), simply because a sufficient standard analysis of knowledge cannot allow for knowledge that is even marginally lucky. (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)

This thesis centers on two trends in epistemology: the dissatisfaction with the reductive analysis of knowledge, the project of explicating knowledge in terms of necessary and jointly sufficient conditions, and the popularity of virtue-theoretic epistemologies. The goal of this thesis is to endorse non-reductive virtue epistemology. Given that prominent renditions of virtue epistemology assume the reductive model, however, such a move is not straightforward—work needs to be done to elucidate what is wrong with the reductive model, in general, (...) and why reductive accounts of virtue epistemology, specifically, are lacking. The first part of this thesis involves diagnosing what is wrong with the reductive model and defending that diagnosis against objections. The problem with the reductive project is the Gettier Problem. In Chapter 1, I lend credence to Linda Zagzebski’s grim 1994 diagnosis of Gettier problems by examining the nature of luck, the key component of Gettier problems. In Chapter 2, I vindicate this diagnosis against a range of critiques from the contemporary literature. The second part involves applying this diagnosis to prominent versions of virtue epistemology. In Chapter 3, we consider the virtue epistemology of Alvin Plantinga. In Chapter 4, we consider the virtue epistemology of Ernest Sosa. Both are seminal and iconic; nevertheless, I argue that, in accord with our diagnosis, neither is able to viably surmount the Gettier Problem. Having diagnosed what is wrong with the reductive project and applied this diagnosis to prominent versions of virtue epistemology, the final part of this thesis explores the possibility of non-reductive virtue epistemology. In Chapter 5, I argue that there are three strategies that can be used to develop non-reductive virtue epistemologies, strategies that are compatible with seminal non-reductive accounts of knowledge and preserve our favorite virtue-theoretic concepts. (shrink)

Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.

Church's Thesis (CT) was first published by Alonzo Church in 1935. CT is a proposition that identifies two notions: an intuitive notion of an effectively computable function defined in natural numbers with the notion of a recursive function. Despite the many efforts of prominent scientists, Church's Thesis has never been disproven. There exists a vast literature concerning the thesis. The aim of this book is to provide a one volume summary of the state of research (...) on Church's Thesis. These include the following: different formulations of CT, CT and intuitionism, CT and intensional mathematics, CT and physics, the epistemic status of CT, CT and philosophy of mind, provability of CT and CT and functional programming. Adam Olszewski, is assistant professor of the philosophy of mathematics and mathematical logic at the Department of Philosophy of Pontifical Academy of Theology, Cracow (Poland). Jan Wolenski is professor of philosophy, Institute of Philosphy, Jagiellonian University, Cracow (Poland). He is one of the most distinguished logicians in Poland. Robert Janusz is assistant professor in the Department of Philosophy of Ignatius College, Cracow (Poland). (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)

We argue that uncomputability and classical scepticism are both reflections of inductive underdetermination, so that Church's thesis and Hume's problem ought to receive equal emphasis in a balanced approach to the philosophy of induction. As an illustration of such an approach, we investigate how uncomputable the predictions of a hypothesis can be if the hypothesis is to be reliably investigated by a computable scientific method.

Wilfred Sieg. “Church's Thesis”, “Consistency”, “Formalization”, “Proof Theory”: Dictionary Entries.

In the very last chapter of my Introduction to Gödel Theorems, I rashly claimed that there is a sense in which we can informally prove Church’s Thesis. This sort of claim isn’t novel to me: but it certainly is still very much the minority line. So maybe it is worth rehearsing some of the arguments again. Even if I don’t substantially add to the arguments in the book, it might help to approach things in a different order, with some (...) different emphases, to make the issue as clear as possible. (shrink)

In the section ‘Further reading’, I listed a book that arrived on my desk just as I was sending IGT off to the press, namely Church’s Thesis after 70 Years edited by Adam Olszewski et al. On the basis of a quick glance, I warned that the twenty two essays in the book did seem to be of ‘variable quality’. But actually, things turn out to be a bit worse than that: the collection really isn’t very good at all! (...) After I sent my book to press, I gave a paper-by-paper review on my blog, at http://logicmatters.blogspot.com. It is probably more fun to chase up the reviews ‘in the wild’, so to speak, starting from the entry for May 14, 2007. But here they are wrapped up into a single document, only marginally tidied. Some of the points made here should help further explain and support the general line on the Thesis taken in.. (shrink)

The article analyses the role of Church’s Thesis (hereinafter CT) in the context of the development of hypercomputation research. The text begins by presenting various views on the essence of computer science and the limitations of its methods. Then CT and its importance in determining the limits of methods used by computer science is presented. Basing on the above explanations, the work goes on to characterize various proposals of hypercomputation showing their relative power in relation to the arithmetic hierarchy. (...) The general theme of the article is the analysis of mutual relations between the content of CT and the theories of hypercomputation. In the main part of the paper the arguments for abolition of CT caused by the introduction of hypercomputable methods in computer science are presented and critique of these views is presented. The role of the efficiency condition contained in the formulation of CT is stressed. The discussion ends with a summary defending the current status of Church’s thesis within the framework of philosophy and computer science as an important point of reference for determining what the notion of effective calculability really is. The considerations included in this article seem to be quite up-to-date relative to the current state of affairs in computer science.1. (shrink)

Under the assumption that all "rules" are recursive (ECT) the statement $\operatorname{Cont}(N^N,N)$ that all functions from N N to N are continuous becomes equivalent to a statement KLS in the language of arithmetic about "effective operations". Our main result is that KLS is underivable in intuitionistic Zermelo-Fraenkel set theory + ECT. Similar results apply for functions from R to R and from 2 N to N. Such results were known for weaker theories, e.g. HA and HAS. We extend not only (...) the theorem but the method, fp-realizability, to intuitionistic ZF. (shrink)

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)

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)

If humans are not capable of immortality, then eschatological doctrines of heaven and hell make little sense. On that Christians agree. But not all Christians agree on whether humans are essentially immortal. Some hold that the early church was right to borrow from the ancient Greek philosophers and to bring their sense of immortality to bear on the interpretation of biblical passages about the afterlife. Others, however, suggest that we are inherently mortal, and only conditionally immortal. This latter view is (...) usually associated with an annihilationist interpretation of the doctrine of hell and a rejection of eternal torment. In a philosophical analysis and argument, McLeod-Harrison proposes that humans are, indeed, immortal, but not essentially so. But neither are we immortal accidentally or conditionally. Instead, immortality is an enduring property--a property we cannot lose once created. McLeod-Harrison carefully delineates the sense of immortality he defends and provides a broadly Christian philosophical argument for it. The argument, if correct, leaves the recent suggestion that the unredeemed are annihilated on unsteady metaphysical feet. However, McLeod-Harrison does not defend eternal conscious punishment for the unredeemed, but suggests some ways to think about the possibility of a universal salvation. ""McLeod-Harrison provides an admirably careful metaphysical analysis of the concept of human immortality, ultimately arguing for the impossibility of personal annihilation. Whether or not one finally agrees with his thesis, this work is an immensely valuable resource, especially as regards discussions of philosophical anthropology and the doctrine of hell."" --James S. Spiegel, Professor of Philosophy and Religion, Taylor University ""In this fascinating, albeit complicated, argument against conditional immortality (annihilationism), the author makes no claim that the human soul is essentially immortal; he argues instead that, once a human offspring acquires a fully robust free will and thus becomes fully human, it is metaphysically impossible that it should cease to exist altogether. Whether or not one accepts every detail of this argument, it provides an original and intriguing twist to theological discussions of free will."" --Thomas Talbott, Professor Emeritus of Philosophy, Willamette University, Author of The Inescapable Love of God ""I often say the future of the hell debate is between conditional immortality and universal reconciliation, and it is no secret that I think the biblical case for the former is unassailable. However, while I am not persuaded by this volume's case for enduring and universal human immortality, it nevertheless promises to add precision to the language of immortality and to feature prominently in the philosophical side of that debate moving forward."" --Christopher M. Date, editor of Rethinking Hell: Readings in Evangelical Conditionalism Mark S. McLeod-Harrison is Professor of Philosophy at George Fox University. (shrink)

In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 1 In some cases it is enough to assume the enumerability of Y while in others the effective enumerability is a substantial demand. These enigmatical words by Kleene were our point of departure: When Church proposed this thesis, I sat down to disprove it by diagonalizing out of the class of the λ–definable functions. But, quickly realizing that the diagonalization (...) cannot be done effectively, I became overnight a supporter of the thesis. (1981, p. 59) The title of our paper alludes to this very work, a task on which Kleene claims to have set out after hearing such a remarkable statement from Church, who was his teacher at the time. There are quite a few points made in this extract that may be surprising. First, it talks about a proof by diagonalization in order to test—in fact to try to falsify—a hypothesis that is not strictly formal. Second, it states that such a proof or diagonal construction fails. Third, it seems to use the failure as a support for the thesis. Finally, the episode we have just described took place at a time, autumn 1933, in which many of the results that characterize Computability Theory had not yet materialized. The aim of this paper is to show that Church and Kleene discovered a way to block a very particular instance of a diagonal construction: one that is closely related to the content of Church's thesis. We will start by analysing the logical structure of a diagonal construction. Then we will introduce the historical context in order to analyse the reasons that might have led Kleene to think that the failure of this very specific diagonal proof could support the thesis. This is a joint paper. We have both attempted to add a small piece to an amazing historical jigsaw puzzle at a juncture we feel to be appropiate. In the paper by Manzano 1997 the aforementioned words by Kleene were quoted, and since then several logicians, Enrique Alonso first and foremost, have questioned her on this issue. Here we both submit our reply. (1999, pp. 249--273). (shrink)

Cet article se veut une critique de la thèse défendue par [Cleland 1993], laquelle soutient que la thèse de Church doit être rejetée puisque les limites du calcul dépendent de la structure physique du monde. Dans un premier temps, nous offrons un bref aperçu de la thèse de Church puis nous présentons l argument de Cleland. Par la suite, nous proposons une analyse critique de son argument, ce qui nous amènera à faire quelques distinctions conceptuelles par rapport aux notions qui (...) concernent la calculabilité. Finalement, nous montrons que les limites du calcul ne sont pas physiques mais bien logiques. En résumé, notre argument est que les limites du calcul sont déterminées en partie par le fait qu’une procédure effective doit pouvoir être décrite de manière finie.Even though Church’s thesis is widely accepted among mathematicians, it is nonetheless controversial. In this paper, we argue against the position of [Cleland 1993], which defends that Church s thesis must be rejected because the limits of computation depend upon the physical structure of the world. We first give a brief overview of Church’s thesis and then we present Cleland s argument. We then propose a critical analysis of Cleland s argu­ment, which will involve some conceptual distinctions regarding the notion of computability, and finally we will show that the limits of computation are not physical but logical. In short, we argue that computation is limited by the fact that an effective procedure must be described in a finite way. (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.

Cet article se veut une critique de la thèse défendue par [Cleland 1993], laquelle soutient que la thèse de Church doit être rejetée puisque les limites du calcul dépendent de la structure physique du monde. Dans un premier temps, nous offrons un (très) bref aperçu de la thèse de Church puis nous présentons l argument de Cleland. Par la suite, nous proposons une analyse critique de son argument, ce qui nous amènera à faire quelques distinctions conceptuelles par rapport aux notions (...) qui concernent la calculabilité. Finalement, nous montrons que les limites du calcul ne sont pas physiques mais bien logiques. En résumé, notre argument est que les limites du calcul sont déterminées en partie par le fait qu’une procédure effective doit pouvoir être décrite de manière finie. (shrink)

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions ; and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his (...) thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a. (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)