On the Relevance of Turing’s Thesis
DOI:
https://doi.org/10.48160/18532330me7.151Keywords:
Turing’s thesis, effective calculation, EntscheidungsproblemAbstract
In this paper we seek to explain the relevance of Turing’s thesis about the concept of effective calculation in relation to Church’s thesis about the same topic. Even though both theses are equivalent extensionally and provide therefore the same solution to Hilbert’s Entscheidungsproblem, there is a kind of agreement in considering that Turing’s formulation is the most satisfactory or the most convincing. The question is why such an agreement exists. In response to this question particular attention is given to the complexity of the Entscheidungsproblem and to the extent to which Church and Turing’s proposals catch that complexity.
References
Church, A. (1965a), “An Unsolvable Problem of Elementary Number Theory”, en Davis, M. (ed.),The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions,NuevaYork: Raven Press, pp. 88 -107.
Church, A. (1965b), “A Note on the Entscheidungsproblem”, en Davis, M. (ed.), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, NuevaYork: Raven Press, pp. 108-115.
Church, A. (2013) “Review: A.M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem”, en Cooper,S.B.yJ. van Leeuwen (eds.), Alan Turing. His Work and Impact, Amsterdam: Elsevier, p.119.
Copeland, J.(ed.) (2004),The Essential Turing, Oxford: Oxford University Press.
Davis, M.(1982),“Why Gödel Didn’t Have Church’s Thesis”,Information and Control54(1): 3-24.
Gandy, R. (1988),“The Confluence of Ideas in 1936”, enHerken,R. (ed.), A Half-century Survey on The Universal Turing Machine, NuevaYork: Oxford Univesity Press, pp. 51-102.
Gödel, K. (1931),“Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, Monatshefte fur Mathematik und Physik38: 173-198.
Gödel, K. (1995),Kurt Gödel: Collected Works,Vol. III, NuevaYork: Oxford University Press.
Hilbert, D. (1902), “Mathematical Problems”, Bulletin of the American Mathematical Society8(10): 437-479.
Hilbert, D. (1967), “On the Infinite”, en Van Heijenoort,J. (ed.), From Frege to Gödel,Cambridge, MA: Harvard University Press, pp. 367-392.
Hilbert, D. (2005), “Axiomatic Thought”, en Ewald, W. (ed.) (2005), From Kant to Hilbert: A Source Book in the Foundations of Mathematics, Vol. 2,Oxford: Clarendon Press, pp. 1105-1115.
Hilbert, D. y W. Ackermann (1950), The Principles of Mathematical Logic, Nueva York: Chelsea Publishing Company.
Kleene, S.C. (1936), “-Definability and Recursiveness”, Duke Mathematical Journal2: 340-353.
Petzold, C. (2008), The Annotated Turing. A Guide Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine, Indianápolis: Wiler Publishing, Inc.
Turing, A. (1965), “On Computable Numbers, with an Application to the Entscheidungs problem”, en Davis, M. (ed.), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Nueva York: Raven Press, pp.115-151.
Webb, J. (1980), Mechanism, Mentalism, and Metamathematics,Dordrech: Reidel.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 Metatheoria – Journal of Philosophy and History of ScienceThe documents published here are governed by the licensing criteria
Creative Commons Argentina.Atribución - No Comercial - Sin Obra Derivada 2.5 https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
