¿Qué es un algoritmo? Una respuesta desde la obra de Wittgenstein
DOI:
https://doi.org/10.5944/endoxa.36.2015.14967Palabras clave:
algorithm, recursor, abstract state machine, Wittgenstein.Resumen
En este trabajo trato de analizar el debate en torno a la pregunta “¿qué es un algoritmo?”. En la actualidad hay dos grandes enfoques representados por Y. Gurevich, quien considera que un algoritmo es una máquina de estados abstracta, y por Y. Moschovakis, quien considera que un algoritmo es un recursor. Mi propuesta es que ambas respuestas a la pregunta pueden subsumirse bajo la concepción de un algoritmo como una serie de formas, propuesta que captura la definición general de algoritmo comúnmente empleada.
Descargas
Citas
Blass, A. & Gurevich, Y. (2007). Abstract state machines capture parallel algorithms: correction and extension, ACM Transactions on Computational Logic, V, 1-29.
Church, A. (1932). A set of postulates for the foundation of logic, The Annals of Mathematics, 33, 346-366.
Church, A. (1936). An unsolvable problem of elementary number theory. In M. Davis (Ed.), The undecidable (pp. 88-107). New York: Raven Press.
Fernández, G. y Sáez, F. (1987). Fundamentos de informática. Madrid: Alianza
Gödel, K. (1934). Sobre sentencias indecidibles de los sistemas formales matemáticos. En Jesús Mosterín (Ed.), Obras Completas (pp. 167-196). Madrid: Alianza.
Gödel, K. (1964). Postscriptum to Gödel 1931. In M. Davis (Ed.), The undecidable (pp. 71-73). New York: Raven Press.
Gurevich, Y. (2000). Sequential abstract state machines capture sequential algorithms, ACM Transactions on Computational Logic, 1, 77-111.
Gurevich, Y. (2011). What is an algorithm?, Technical report MSR-TR-2011-116.
Moschovakis, Y. & Paschalis, V. (2008). Elementary algorithms and their implementations. In S.B. Cooper, B. Löwe, & A. Sorbi (Eds.), New computational paradigms (pp. 87-118). Springer.
Moschovakis, Y. (1998). On founding the theory of algorithms. In H.G. Dales, & G. Oliveri (Eds.), Truth in mathematics (pp. 71-104). Oxford University Press.
Moschovakis, Y. (2001). What is an algorithm? in B. Engquist & W. Schmid (Eds.), Mathematics Unlimited: 2001 and Beyond (pp. 919-936). Berlin: Springer.
Shanker, S.G. (1987). Wittgenstein versus Turing on nature of Church’s thesis, Notre Dame Journal of Formal Logic, 28, 615-649.
Sieg, W. (2006). Gödel on computability, Philosphia Mathematica, III, 189-207.
Soare, R. (2009). Turing oracles machines, online computing, and three displacements in computability theory, Annals of Pure and Applied Logic, 160, 368-399.
Turing, A. (1936). On computable numbers, with an application to the Entscheidungsproblem. In M. Davis (Ed.), The undecidable (pp. 116-151). New York: Raven Press.
Vardi, M. Y. (2012). What is an algorithm? Communications of the ACM, 5(3), 5.
Wittgenstein, L. (1922). Tractatus logico-philosophicus. London: Routledge.
Wittgenstein, L. (1974). Philosophical grammar. Traducción de Luis F. Segura, ed. 1992. México, D.F.: UNAM.
