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||No keywords specified (fix it)|
|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 (forthcoming). Another Approach: The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Gödel, Turing, 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. Minds and Machines 18 (3).
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 downloads67 ( #13,279 of 549,130 )
Recent downloads (6 months)1 ( #63,397 of 549,130 )
How can I increase my downloads?