THERMOGAMAS - Theory of Computation and Dynamical Systems (Daniel Graça) (1/3)

Talk given during the THERMOGAMAS Workshop.

Abstract: In this talk we will explore interconnections between the theory of computation and dynamical systems. We will begin by providing simple examples and their underlying motivation to demonstrate the interest of this approach, and we will then proceed to review concepts and notions from the theory of computation and from dynamical systems theory.

We continue by taking two complementary perspectives to connect the theory of computation with dynamical systems theory, with an emphasis on continuous-time dynamical systems. We start by analyzing several results from dynamical systems theory from a computational perspective, where the objective is to understand how complex dynamical phenomena can be from a computational perspective. We will see that algorithmic hardness is an independent source of complex behavior for dynamical systems. In the second perspective, we consider classes of dynamical systems that are able by themselves to perform computation, and we relate their computational power to classical (discrete) models of computation, to gain further insights between the connections of the theory of computation and dynamical systems theory.