Dynamical Systems and Computation: a logical approach – DySCo

DySCo will build on Seiller's theory of Interaction Graphs to revisit the foundations for computer science using the mathematics of dynamical systems. Indeed, Seiller’s work shows how graphings – a generalisation of dynamical systems – provide an expressive and powerful mathematical model of computer programs. DySCo will draw out satisfying definitions for the notions of computation, programs and algorithms in a way that will be both general enough to encompass various models of computation and precise enough to provide algorithmically complete models. These theoretical foundations will allow the expansion of the relationship between logic and computation, enabling the Curry-Howard toolbox beyond its current limits. They will also allow the transfer of tools and methods from the mathematical theory of dynamical systems to be used in computer science, notably for proving lower bounds results in computational complexity.