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

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
Keywords effective computation   recursiveness   computable functions   Church's Thesis   Turing's Thesis   abstract state machines   algorithms   encodings
Categories (categorize this paper)
DOI 10.2178/bsl/1231081370
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,043
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
The Concept of Truth in Formalized Languages.Alfred Tarski - 1936 - 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.
A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.

View all 30 references / Add more references

Citations of this work BETA

Copeland and Proudfoot on Computability.Michael Rescorla - 2012 - Studies in History and Philosophy of Science Part A 43 (1):199-202.
Turing Machines.David Barker-Plummer - 2008 - Stanford Encyclopedia of Philosophy.
Foundational Analyses of Computation.Yuri Gurevich - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 264--275.

View all 16 citations / Add more citations

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 index

Total views
182 ( #63,440 of 2,498,582 )

Recent downloads (6 months)
5 ( #140,198 of 2,498,582 )

How can I increase my downloads?


My notes