Another Approach: The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem
In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Gödel, Turing, Church, and beyond. MIT Press (forthcoming)
| Abstract | The present paper was originally conceived on reading Soare (1996). The beauty power and obvious fundamental importance of Turing’s analysis of human computation (what he calls “argument I”) has led to an almost exclusive emphasis on this argument as the unique justification for the Church-Turing thesis. In this paper I advocate an alternative justification, essentially proposed 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. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links | This entry has no external links. Add one. |
| Through your library | Configure |
Similar books and articlesDavid Israel (2002). Reflections on Gödel's and Gandy's Reflections on Turing's Thesis. Minds and Machines 12 (2):181-201.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. Minds and Machines 18 (3).
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Itamar Pitowsky (2002). Quantum Speed-Up of Computations. Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
John T. Kearns (1997). Thinking Machines: Some Fundamental Confusions. Minds and Machines 7 (2):269-87.
Nachum Dershowitz & Yuri Gurevich (2008). A Natural Axiomatization of Computability and Proof of Church's Thesis. Bulletin of Symbolic Logic 14 (3):299-350.
Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-06-18Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
