David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Jörgen Sjögren (2010). A Note on the Relation Between Formal and Informal Proof. Acta Analytica 25 (4):447-458.
Nir Fresco (2013). Information Processing as an Account of Concrete Digital Computation. Philosophy and Technology 26 (1):31-60.
Hector Zenil (2013). What Is Nature-Like Computation? A Behavioural Approach and a Notion of Programmability. Philosophy and Technology (3):1-23.
Michael Rescorla (2012). Copeland and Proudfoot on Computability. Studies in History and Philosophy of Science Part A 43 (1):199-202.
Similar books and articles
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Tim Button (2009). SAD Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
R. Urbaniak (2011). How Not To Use the Church-Turing Thesis Against Platonism. Philosophia Mathematica 19 (1):74-89.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Oron Shagrir (2002). Effective Computation by Humans and Machines. Minds and Machines 12 (2):221-240.
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Saul A. Kripke (2013). The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond. MIT Press.
Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Added to index2009-02-05
Total downloads74 ( #21,502 of 1,140,266 )
Recent downloads (6 months)2 ( #86,093 of 1,140,266 )
How can I increase my downloads?