The notion of algorithm, which predates even the earliest developments of computer science, is nowadays omnipresent in our digitalised society. However, no consensus exists as to what an algorithm is. Even if computer scientists have an intuitive idea of what an algorithm is in the context of informatics, no formal definition exists.

This meeting will gather researchers in computer science, mathematical logic, and philosophy of science around this question of formalising the notion of algorithm. Indeed, the question is fundamentally interdisciplinary as such a formalisation should be accompanied with a conceptual delimitation of the concept. The lack of formal definition of the notion of algorithm has been observed for many years, notably by Richard Shore who identified it in 2001 as one of three remaining "not original and probably pie-in-the-sky" problems. In particular, it lead to proposals for such formalisation: Y. Gurevich introduced the notion of abstract state machines, and Y. Moschovakis introduced the notion of recursors. More recently, T. Seiller proposed a new formalisation, based on work in program semantics and computational complexity. The objective of the meeting will be to compare these approaches from a mathematical and a conceptual point of view, as well as through a confrontation with computer science practice.

Creative Commons BY 4.0

Alberto Naibo and Thomas Seiller