Talk: Philippos Papayannopoulos (CNRS)

Title:

Algorithms and Computations as Dynamical Systems. A Formal Approach to Restoring an Old Peace

Abstract:

How are the concepts of “computation” and “algorithm” related? The classical view is that both terms denote virtually the same thing. “Computation” refers to a mechanical, step-by-step, deterministic process for obtaining a mathematical value, and “algorithm” refers either to the same process or to the set of instructions that specify this process. While this is a well-entrenched view in logic and computer science, I argue that it stands in contrast with how algorithms are used in numerical analysis and other areas of math. Thus, I propose a distinction between two different conceptions of “algorithms” and discuss some features that I think make the two conceptions genuinely irreducible to each other. I also propose that by drawing upon the theory of discrete dynamical systems (DDS) we can treat both conceptions in a new and unified way. This is because at the heart of both notions of algorithms lies the idea of iteration, which is also central in DDS. Finally, I briefly explore the prospects of extending this approach to the case of continuous dynamical systems and continuous computations.