A natural axiomatization of computability and proof of Church’s thesis

Bulletin of Symbolic Logic 14 (3):299-350 (2008)
  Copy   BIBTEX


Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers



    Upload a copy of this work     Papers currently archived: 77,805

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

Computability and recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Is the church-Turing thesis true?Carol E. Cleland - 1993 - Minds and Machines 3 (3):283-312.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
How Not To Use the Church-Turing Thesis Against Platonism.R. Urbaniak - 2011 - Philosophia Mathematica 19 (1):74-89.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.


Added to PP

191 (#70,122)

6 months
5 (#167,582)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Copeland and Proudfoot on computability.Michael Rescorla - 2012 - Studies in History and Philosophy of Science Part A 43 (1):199-202.
Explication as a Three-Step Procedure: the case of the Church-Turing Thesis.Matteo De Benedetto - 2021 - European Journal for Philosophy of Science 11 (1):1-28.
Turing machines.David Barker-Plummer - 2008 - Stanford Encyclopedia of Philosophy.

View all 18 citations / Add more citations

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
The concept of truth in formalized languages.Alfred Tarski - 1931 - In A. Tarski (ed.), Logic, Semantics, Metamathematics. Oxford University Press. pp. 152--278.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
Grundzüge der theoretischen Logik.D. Hilbert & W. Ackermann - 1928 - Annalen der Philosophie Und Philosophischen Kritik 7:157-157.

View all 37 references / Add more references