Graduate studies at Western
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)|
|Through your library||Configure|
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 downloads71 ( #14,731 of 739,080 )
Recent downloads (6 months)4 ( #20,702 of 739,080 )
How can I increase my downloads?