Algorithms and Ontology
Walter Dean  1  
1 : Warwick University, Department of Philosophy

The broad goal of this paper is to bring to the attention of philosophers of mathematics and computation the concept of \textsl{algorithm} (e.g Euclid's algorithm, Strassen's algorithm, the Gröbner basis algorithm) as it is studied in contemporary theoretical computer science, and at the same time address several foundational questions about the role this notion plays in mathematical practice. A variety of considerations such as the need to prove correctness and provide running time analyses suggest that algorithms ought to be assimilated to mathematical objects such as models of computation or recursion schemes -- a view which is embodied by the well-known proposals of Yiannis Moschovakis and Yuri Gurevich. I will suggest instead that a variety of considerations grounded in complexity theory and algorithmic analysis serve as in principle obstacles to making such an identification.


Online user: 1