Speaker
Description
Turing machines have traditionally been studied as computational models, but we center our line of research on the dynamical properties of Turing machines, thus focusing on their behavior rather than the final results. This approach, in the context of Turing machines, has been fruitful since its inception by K ̊urka in 1997 [2], with studies on immortality [4, 5], entropy, equicontinuity, periodicity and, recently, transitivity and minimality [1, 3]. The existence of a Topological Transitive and Topological Minimal Turing machine was presented recently [1], concepts ligated to reaching finite configurations in the orbits
of the Turing machine. Nevertheless, Mixing notions have not been studied in this field. Total Transitivity, Weak Mixing and Topological Mixing endorse time restriction to reaching finite configurations inside the orbits of the machine, therefore requiring a deeper understanding on the dynamics of the studied machines. Although, known Turing machines with all the previous properties have very simple dynamics. In this presentation, we prove that the complex machine SMART [1] presents the property Topological Mixing.
[1] J. Cassaigne, N. Ollinger and R. Torres-Aviles. A Small Minimal Ape-riodic Reversible Turing Machine. Journal of Computer and System Science, 84C:288-301, 2017.
[2] P. K ̊urka. On topological dynamics of Turing machines. Theoretical Computer Science, 174(1-2):203-216, 1997.
[3] A. Gajardo, N. Ollinger and R. Torres-Aviles. The Transitivity Problem of Turing Machines. Mathematical Foundation of Computer Science 2015 (Milano, Italy) Lecture Notes of Computer Science, 9234:231-242, 2015.
[4] J. Kari and N. Ollinger. Periodicity and Immortality in Reversible Computing. Mathematical Foundation of Computer Science 2008 (Roun, Poland) Lecture Notes of Computer Science, 5162:419-430, 2008.
[5] E. Jeandel. On immortal configurations in Turing machines. Conference on Computability in Europe 2012 (Cambrige, UK) Lecture Notes of Computer Science, 7318:334-343, 2012.