Is the church-Turing thesis true?
Minds and Machines 3 (3):283-312 (1993)
| 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) | |||||||||
| Keywords | Causality Church's Thesis Procedure Science Turing Machines | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,875 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJeremy Seligman (2002). The Scope of Turing's Analysis of Effective Procedures. Minds and Machines 12 (2):203-220.
Itamar Pitowsky (2002). Quantum Speed-Up of Computations. Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. Minds and Machines 18 (3).
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
John T. Kearns (1997). Thinking Machines: Some Fundamental Confusions. Minds and Machines 7 (2):269-87.
Carol E. Cleland (1995). Effective Procedures and Computable Functions. Minds and Machines 5 (1):9-23.
Leon Horsten (1995). The Church-Turing Thesis and Effective Mundane Procedures. Minds and Machines 5 (1):1-8.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads76 ( #10,907 of 556,837 )Recent downloads (6 months)4 ( #20,489 of 556,837 )How can I increase my downloads? |
My notes
Discussion
