What is an Algorithm? An Answer Based on Wittgenstein’s Work
DOI:
https://doi.org/10.5944/endoxa.36.2015.14967Keywords:
algorithm, recursor, abstract state machine, Wittgenstein.Abstract
In this paper, I will try to analyze the debate on the question “What is an algorithm?” Currently, there are two main approaches represented by Y. Gurevich, who considers that an algorithm is an abstract state machine, and by Y. Moschovakis, who thinks that an algorithm is a recursor. My proposal is that both approaches to the question can be subsumed under the notion of an algorithm as a series of forms. This proposal captures the general definition of algorithm that is commonly employed.Downloads
References
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.
Downloads
Published
How to Cite
Issue
Section
License
The authors who publish in this journal must agree to the following terms:
- The authors hold author’s rights and guarantee the journal the right to be the first to publish the work as well as the Creative Commons Attribution License which allows others to share the work as long as they acknowledge the authorship of the work and its initial publication in this journal.
- The authors can establish, on their own, additional agreements for the non-exclusive distribution of the version of the work published in the journal (for example, placing it in an institutional repository or publishing it in a book), always acknowledging the initial publication in this journal.
- The authors are allowed and encouraged to disseminate their work electronically (for example, in institutional repositories or on their own webpages) before and during the submission process, as this can give rise to productive exchanges, as well as earlier and increased citing of the works published (See The Effect of Open Access).
