Preprint 2018-39
Anahi Gajardo, Nicolas Ollinger, Rodrigo Torres:
Transitivity and minimality in the context of Turing machine topological models
Abstract:
Turing machines are studied as dynamical systems since two decades ago. Several results concerning topological properties such as equicontinuity, periodicity, mortality, entropy, etc. has been established. These properties strongly depend on the topological model that one consider, and for Turing machines two main models are pertinent. Here we focus on transitivity, minimality and other adjacent properties. In the context of Turing machines, transitivity means that there exists a con guration whose evolution contains every possible con guration over any nite window. Minimality means that every con guration ful lls this, and is a very strong property. This paper establishes the exact relations existing between four main properties: transitivity, minimality, existence of blocking words, and reversibility; showing examples on each non empty class at the intersection of these properties. It also develops the embedding technique, that combines two Turing machines to produce a third one that, under some particular conditions, will inherit the properties of one of the original machines. This powerful tool is used to establish undecidability results and also to multiply the number of examples that we have found.
