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

Abstract
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
Options
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: 62,473
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

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

View all 15 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.

Analytics

Added to PP index
2009-02-05

Total views
177 ( #58,750 of 2,446,288 )

Recent downloads (6 months)
1 ( #456,806 of 2,446,288 )

How can I increase my downloads?

Downloads

My notes