Thesis Summary:

This doctoral thesis is centered on the study of the dynamical properties concerning Turing machines. A Turing machine is quite simple, yet powerful, consisting in a bi-infinite tape of finite alphabet, finite internal states, a head pointing an unique position on the tape and under finite instructions. If the symbol under the head and the internal state match with any instruction, then it is applied, exchanging the symbol, the internal state, and moving the head one position to the left or the right. The Turing machine is the main mechanical model to study computation. As computation is a powerful tool to study large phenomena as the dynamic, therefore it is interesting and fruitfully to study dynamic through Turing machine. It is not quite natural to see Turing machines as dynamical system, mainly due to headless configurations, as it is on other computation models (as cellular automata), therefore it is tackled from three different systems. The first is commonly called Turing machine with Moving Head (TMH), when the evolution is performed by moving the head, other called Turing machine with Moving Tape (TMT), where it evolves by moving the tape instead of the head, and another one called t-shift, which consist in words of pairs symbol-state, viewing only the content of the head and the internal state in orbits of configurations, and it evolves shifting the words. The object of the thesis is to study some open questions regarding specific Turing machine dynamical systems, as surjectivity, periodicity in complete and reversible machines, topological entropy, topological transitivity and topological minimality. The surjectivity in Turing machine is quite easy to decide, but this is not inherited by its t-shift dynamical system. To address this matter, it is defined a new concept called blocking words, which is a finite configuration that does not allow the head to visit a certain part of the tape. We prove that having a blocking word in a Turing machine is an undecidable question. Through a reduction from the previous problem, it is then possible to show that the surjectivity is an undecidable property for the t-shift. We prove, using an adaptation of the proof for blocking words that it is undecidable to know if a Turing machine has a positive entropy or not. Later on, we study a machine created by Julien Cassaigne that we call SMART, and we prove that it has several good properties, as being aperiodic, time symmetric, transitive in all three dynamical models, minimal in TMT and with a substitutive t-shift. This machine is the first example of complete and reversible machine that has a transitive TMH dynamical model, a minimal TMT and t-shift dynamical model and it has not a periodic orbit. We show that its existence allows to study in depth the former matters. With a technique, called embedding, we prove the undesirability of aperiodicity and transitivity on Turing machine dynamical systems by using a reduction from the emptiness and mortality problems. We also prove the undesirability of minimality for TMT and t-shift, but no for TMH, as there is no minimal TMH machine. We go further in the study of transitivity by showing that the classes of machines with transitive TMH, TMT and t-shift system are nested and we exhibit examples that prove the inclusions are strict. In the transitive context, we study that class of the coded systems. We exhibit examples to show the diversity of the known subclasses of the coded systems inside t-shifts.

ISI Publications from the Thesis

Anahi GAJARDO, Nicolas OLLINGER, Rodrigo TORRES: Some undecidable problems about the trace-subshift associated to a Turing machine. Discrete Mathematics & Theoretical Computer Science, vol. 17, 2, pp. 267-284, (2015).

No-ISI Publications from the Thesis

Anahi GAJARDO, Nicolas OLLINGER, Rodrigo TORRES: Undecidability of the surjectivity of the subshift associated to a Turing machine. Lecture Notes in Computer Science, vol. 7581, pp. 44-56, (2012).