The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem

In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond. MIT Press (2013)
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.
Keywords Church-Turing Thesis  Gödel’s completeness theorem  Entscheidungsproblem
Categories (categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,411
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

161 ( #26,255 of 1,924,713 )

Recent downloads (6 months)

16 ( #40,232 of 1,924,713 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.