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

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,998

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 - 2014 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Stanford, CA: The Metaphysics Research Lab.
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
2009-02-05

Downloads
230 (#87,836)

6 months
33 (#102,974)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Decision Problem for Effective Procedures.Nathan Salmón - 2023 - Logica Universalis 17 (2):161-174.
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.

View all 19 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.
Grundzüge der theoretischen Logik.D. Hilbert & W. Ackermann - 1928 - Annalen der Philosophie Und Philosophischen Kritik 7:157-157.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.

View all 39 references / Add more references