Is the church-Turing thesis true?

Minds and Machines 3 (3):283-312 (1993)
  Copy   BIBTEX

Abstract

  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)

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,346

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Quantum speed-up of computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.

Analytics

Added to PP
2009-01-28

Downloads
199 (#64,852)

6 months
1 (#450,993)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Carol Cleland
University of Colorado, Boulder

Citations of this work

A connectionist theory of phenomenal experience.Jonathan Opie & Gerard O'Brien - 1999 - Behavioral and Brain Sciences 22 (1):127-148.
The Tractable Cognition Thesis.Iris Van Rooij - 2008 - Cognitive Science 32 (6):939-984.
Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.

View all 35 citations / Add more citations

References found in this work

Minds, brains, and programs.John Searle - 1980 - Behavioral and Brain Sciences 3 (3):417-57.
The emperor’s new mind.Roger Penrose - 1989 - Oxford University Press.
Computing machinery and intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
The Direction of Time.Hans Reichenbach - 1956 - Dover Publications.
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 29 references / Add more references