Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 21 Janvier 2014

Turing machines seen as dynamical systems

par 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.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30