Sobre la relevancia de la tesis de Turing
DOI:
https://doi.org/10.48160/18532330me7.151Palabras clave:
tesis de Turing, cálculo efectivo, EntscheidungsproblemResumen
En este artículo intentamos dar cuenta de la relevancia de la tesis de Turing sobre el concepto de cálculo efectivo en relación con la tesis de Church sobre el mismo tema. Si bien ambas tesis son extensionalmente equivalentes y proporcionan, por lo tanto, una misma solución al Entscheidungsproblem de Hilbert, hay una especie de acuerdo en considerar que la formulación de Turing es la más satisfactoria o la más convincente. La pregunta es por qué se da tal acuerdo. En respuesta a esta pregunta destacamos la complejidad del Entscheidungsproblem e indagamos en qué medida las propuestas de Church y Turing captan dicha complejidad.
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2017 Metatheoria – Revista de Filosofía e Historia de la CienciaLos documentos aquí publicados se rigen bajos los criterios de licencia Creative Commons Argentina.Atribución - No Comercial - Sin Obra Derivada 2.5
