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)

There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing thesis is often misunderstood, particularly in recent writing in the philosophy of mind.

We critically discuss Cleland''s analysis of effective procedures as mundane effective procedures. She argues that Turing machines cannot carry out mundane procedures, since Turing machines are abstract entities and therefore cannot generate the causal processes that are generated by mundane procedures. We argue that if Turing machines cannot enter the physical world, then it is hard to see how Cleland''s mundane procedures can enter the world of numbers. Hence her arguments against versions of the Church-Turing thesis for number theoretic (...) functions miss the mark. (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)

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)

The Church–Turing Thesis (CTT) is often employed in arguments for computationalism. I scrutinize the most prominent of such arguments in light of recent work on CTT and argue that they are unsound. Although CTT does nothing to support computationalism, it is not irrelevant to it. By eliminating misunderstandings about the relationship between CTT and computationalism, we deepen our appreciation of computationalism as an empirical hypothesis.

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)

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)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a (...) Turing machine. I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

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

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)

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)

It is commonly believed that there is no equivalent of the Church–Turing thesis for computation over the reals. In particular, computational models on this domain do not exhibit the convergence of formalisms that supports this thesis in the case of integer computation. In the light of recent philosophical developments on the different meanings of the Church–Turing thesis, and recent technical results on analog computation, I will show that this current belief confounds two distinct issues, namely (...) the extension of the notion of effective computation to the reals on the one hand, and the simulation of analog computers by Turing machines on the other hand. I will argue that it is possible in both cases to defend an equivalent of the Church–Turing thesis over the reals. Along the way, we will learn some methodological caveats on the comparison of different computational models, and how to make it meaningful. (shrink)

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)

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)

One of us has previously argued that the Church-Turing Thesis (CTT), contra Elliot Mendelson, is not provable, and is — light of the mind’s capacity for effortless hypercomputation — moreover false (e.g., [13]). But a new, more serious challenge has appeared on the scene: an attempt by Smith [28] to prove CTT. His case is a clever “squeezing argument” that makes crucial use of Kolmogorov-Uspenskii (KU) machines. The plan for the present paper is as follows. After covering some necessary (...) preliminaries regarding the nature of CTT, and taking note of the fact that this thesis is “intrinsically cognitive” (§2), we: sketch out, for context, an open-minded position on CTT and related matters (§3); explain the formal structure of squeezing arguments (§4); after a review of KU-machines, formalize Smith’s case (§5); give our objections to certain assumptions in Smith’s argument (§6); support these objections with some evidence from general but limited-agent problem solving (§7); and explain why Smith’s argument is inconclusive (§8). We end with some brief, concluding remarks, some of which point toward near-future work that will build on the present paper (§9). (shrink)

Olszewski claims that the Church-Turing thesis can be used in an argument against platonism in philosophy of mathematics. The key step of his argument employs an example of a supposedly effectively computable but not Turing-computable function. I argue that the process he describes is not an effective computation, and that the argument relies on the illegitimate conflation of effective computability with there being a way to find out . ‘Ah, but,’ you say, ‘what’s the use of its being right (...) twice a day, if I can’t tell when the time comes?’ Why, suppose the clock points to eight o’clock, don’t you see that the clock is right at eight o’clock? Consequently, when eight o’clock comes round your clock is right. Lewis Carroll. (shrink)

La Teoría de la Computación es un campo especialmente rico para la indagación filosófica. EI debate sobre el mecanicismo y la discusión en torno a los fundamentos de la matemática son tópicos que estan directamente asociados a la Teoria de la Computación desde su misma creación como disciplina independiente. La Tesis de Turing-Church constituye uno de los resultados mas característicos en este campo estando, además, lleno de consecuencias filosóficas. En este ensayo se ofrece una guía de referencia útil a aquellos (...) que desean prestar alguna atención a estos asuntos y carecen de la base técnica o histórica que se precisa. En primer lugar se ofrece un resurnen de los principales problemas relacionados con la Tesis de Turing-Church para ofrecer a continuación información sobre sus aspectos más controvertidos. Se proponen algunos problemas no resueltos y se analiza su relevancia filosófica.Computer Science is a field specially rich for philosophical inquiry. Mechanism and the discussion around foundations of mathematics are topics directly asociated to Computer Science for its very constitution as an independent discipline. Church-Turing Thesis is one of the most characteristic results in this field and is plenty of philosophical consequences. In this article I offer a referenee guide useful for those who are willing to pay some attention to these matters and ignore the technical and historical basis needed for this task. I resume the main topics related to Church-Turing Thesis and give some informationabout the most controversial aspects of this subject. Some open questions are settled for further investigation paying special attention to their philosophical importance. (shrink)

This article is a methodological discussion of formal approaches to the question of identity of proofs from a philosophical standpoint. First, an introduction to the question of identity of proofs itself is given, followed by a brief reconstruction of the so-called normalisation thesis, proposed by Dag Prawitz in 1971, in which some of its core mathematical and conceptual traits are presented. After that, a comparison between the normalisation thesis and the more well-known Church-Turing thesis on computability is (...) carried out in three main parts: the first dedicated to highlighting some of the analogies between them; the second, their most remarkable differences; and the third, to the possible relations of dependence between the two. Based on these considerations, some concluding remarks concerning the potential of the normalisation thesis and similar approaches to the question of identity of proofs are made in the last section. (shrink)

In recent years two different axiomatic characterizations of the intuitive concept of effective calculability have been proposed, one by Sieg and the other by Dershowitz and Gurevich. Analyzing them from the perspective of Carnapian explication, I argue that these two characterizations explicate the intuitive notion of effective calculability in two different ways. I will trace back these two ways to Turing’s and Kolmogorov’s informal analyses of the intuitive notion of calculability and to their respective outputs: the notion of computorability and (...) the notion of algorithmability. I will then argue that, in order to adequately capture the conceptual differences between these two notions, the classical two-step picture of explication is not enough. I will present a more fine-grained three-step version of Carnapian explication, showing how with its help the difference between these two notions can be better understood and explained. (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)

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)

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)

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)

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.

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)

Writings, including articles, letters, and unpublished work, by one of the twentieth century's most influential figures in mathematical logic and philosophy. Alonzo Church's long and distinguished career in mathematics and philosophy can be traced through his influential and wide-ranging writings. Church published his first article as an undergraduate at Princeton in 1924 and his last shortly before his death in 1995. This volume collects all of his published articles, many of his reviews, his monograph The Calculi of Lambda-Conversion, the introduction (...) to his important and authoritative textbook Introduction to Mathematical Logic, a substantial amount of previously unpublished work (including chapters for the unfinished second volume of Introduction to Mathematical Logic), and a selection of letters to such correspondents as Rudolf Carnap and W. V. O. Quine. With the exception of the reviews, letters, and unpublished work, these appear in chronological order, for the most part in the format in which they were originally published. Church's work in calculability, especially the monograph on the lambda-calculus, helped lay the foundation for theoretical computer science; it attracted the interest of Alan Turing, who later completed his PhD under Church's supervision. (Church coined the term “Turing machine” in a review.) Church's influential textbook, still in print, defined the field of mathematical logic for a generation of logicians. In addition, his close connection with the Association for Symbolic Logic and his many years as review editor for the Journal of Symbolic Logic are documented in the reviews included here. (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.

The aim of the paper is to present the underlying reason of the unsolved symbol grounding problem. The Church-Turing Thesis states that a physical problem, for which there is an algorithm of solution, can be solved by a Turing machine, but machine operations neglect the semantic relationship between symbols and their meaning. Symbols are objects that are manipulated on rules based on their shapes. The computations are independent of the context, mental states, emotions, or feelings. The symbol processing operations (...) are interpreted by the machine in a way quite different from the cognitive processes. Cognitive activities of living organisms and computation differ from each other, because of the way they act in the real word. The result is the problem of mutual understanding of symbol grounding. (shrink)

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis, according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently (...) so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why—how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify. In this paper I articulate this question and consider several tentative answers to it. (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)

La Teoría de la Computación es un campo especialmente rico para la indagación filosófica. EI debate sobre el mecanicismo y la discusión en torno a los fundamentos de la matemática son tópicos que estan directamente asociados a la Teoria de la Computación desde su misma creación como disciplina independiente. La Tesis de Turing-Church constituye uno de los resultados mas característicos en este campo estando, además, lleno de consecuencias filosóficas. En este ensayo se ofrece una guía de referencia útil a aquellos (...) que desean prestar alguna atención a estos asuntos y carecen de la base técnica o histórica que se precisa. En primer lugar se ofrece un resurnen de los principales problemas relacionados con la Tesis de Turing-Church para ofrecer a continuación información sobre sus aspectos más controvertidos. Se proponen algunos problemas no resueltos y se analiza su relevancia filosófica.Computer Science is a field specially rich for philosophical inquiry. Mechanism and the discussion around foundations of mathematics are topics directly asociated to Computer Science for its very constitution as an independent discipline. Church-Turing Thesis is one of the most characteristic results in this field and is plenty of philosophical consequences. In this article I offer a referenee guide useful for those who are willing to pay some attention to these matters and ignore the technical and historical basis needed for this task. I resume the main topics related to Church-Turing Thesis and give some informationabout the most controversial aspects of this subject. Some open questions are settled for further investigation paying special attention to their philosophical importance. (shrink)

Accelerating Turing machines are Turing machines of a sort able to perform tasks that are commonly regarded as impossible for Turing machines. For example, they can determine whether or not the decimal representation of contains n consecutive 7s, for any n; solve the Turing-machine halting problem; and decide the predicate calculus. Are accelerating Turing machines, then, logically impossible devices? I argue that they are not. There are implications concerning the nature of effective procedures and the theoretical limits of computability. Contrary (...) to a recent paper by Bringsjord, Bello and Ferrucci, however, the concept of an accelerating Turing machine cannot be used to shove up Searle's Chinese room argument. (shrink)

Alan Turing anticipated many areas of current research incomputer and cognitive science. This article outlines his contributionsto Artificial Intelligence, connectionism, hypercomputation, andArtificial Life, and also describes Turing's pioneering role in thedevelopment of electronic stored-program digital computers. It locatesthe origins of Artificial Intelligence in postwar Britain. It examinesthe intellectual connections between the work of Turing and ofWittgenstein in respect of their views on cognition, on machineintelligence, and on the relation between provability and truth. Wecriticise widespread and influential misunderstandings of theChurch–Turing (...) class='Hi'>thesis and of the halting theorem. We also explore theidea of hypercomputation, outlining a number of notional machines thatcompute the uncomputable. (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)