Anahí Gajardo (Universidad de Concepción, Chile)

Predicting the behaviour of a given system is something that is difficult in general. From dynamical systems point of view, sensitivity to initial conditions is one of the main factors that avoids predictability. From computer sciences, the complexity of the process can avoid predictions, even if all the information about the initial conditions is available.

These two approaches are joined when we study the predictability of a given dynamical system, frequently we try to embed a Turing machine (or a logical circuit) inside the dynamical systems so as to prove that certain questions about the system are undecidable. Usually the halting problem is reduced to some property of the system, such as “reachability” of a given limit point, for example.

In this talk, we consider the Turing machine itself as a dynamical system and we apply the tools of this domain to the study of machines. As a result of this exercise, we can see that several complexity notions are translated in very natural dynamical properties, in particular from the point of view of Chomsky hierarchy. Also natural questions of discrete dynamical systems, as “existence of a periodic orbit”, result to be undecidable in the context of Turing machines.