In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond. MIT Press (2013)
Authors |
|
Abstract |
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) |
Buy the book |
Find it on Amazon.com
|
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
No references found.
Citations of this work BETA
Counterpossibles in Science: The Case of Relative Computability.Matthias Jenny - 2018 - Noûs 52 (3):530-560.
Hybrid Identities and Just Being Yourself.Gillian Russell - 2014 - Inquiry: An Interdisciplinary Journal of Philosophy 57 (4):455-465.
Similar books and articles
Reflections on Gödel's and Gandy's Reflections on Turing's Thesis.David Israel - 2002 - Minds and Machines 12 (2):181-201.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
A Natural Axiomatization of Computability and Proof of Church’s Thesis.Nachum Dershowitz & Yuri Gurevich - 2008 - Bulletin of Symbolic Logic 14 (3):299-350.
Thinking Machines: Some Fundamental Confusions. [REVIEW]John T. Kearns - 1997 - Minds and Machines 7 (2):269-87.
Quantum Speed-Up of Computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW]Eli Dresner - 2008 - Minds and Machines 18 (3):349-355.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Analytics
Added to PP index
2010-06-18
Total views
335 ( #23,355 of 2,409,938 )
Recent downloads (6 months)
7 ( #102,247 of 2,409,938 )
2010-06-18
Total views
335 ( #23,355 of 2,409,938 )
Recent downloads (6 months)
7 ( #102,247 of 2,409,938 )
How can I increase my downloads?
Downloads