Topological mixing notions on Turing machine dynamical systems
A Turing machine \(M = (Q, \Sigma, \delta, \ldots)\) may be regarded as a dynamical system on the space \(Q \times \Sigma^{\mathbf Z}\), and one may investigate the trajectory of the system starting at some \((q, w) \in Q \times \Sigma^{\mathbf Z}\) (see [\textit{P. Kůrka}, Theor. Comput. Sci. 174, No. 1--2, 203--216 (1997; Zbl 0902.68064)]). This article concerns the dynamics of computations of the SMART Turing machine introduced in [\textit{J. Cassaigne} et al., J. Comput. Syst. Sci. 84, 288--301 (2017; Zbl 1410.68121)], and presumes the ``Turing Machine with Movable Tape (TMT) model: the tapehead is fixed (at the \(0\) position) and the tape is moved back and forth so that, for example, given \(w\) with \(w(0) = 1\) and \(z \neq 0 \implies w(z) = 0\), with \(\delta(q, 1) = (q', 2, \mbox{Right})\), the machine moves from configuration \((q, w)\) to \((q', w')\), where \(w(-1) = 2\) and \(z \neq -1 \implies w(z) = 0\). Let \(T : Q \times \Sigma^{\mathbf Z} \to Q \times \Sigma^{\mathbf Z}\) be the transformation induced by the SMART machine; for the SMART machine, \(Q\) has four elements and \(\Sigma\) has three. The first relevant result in this article is that \(T\) is totally transitive (i.e., for each \(n \in \mathbf Z^+\), \(T^n\) is transitive) and weakly mixing (i.e., \(T \times T\) is transitive). The second relevant result is that for Turing machines using the TMT model, whether or not the transformation \(T\) for the given machine is topological mixing (i.e., for open subsets \(U, V \subseteq Q \times \Sigma^{\mathbf Z}\), there exists \(n\) such that for all \(N > n\), \(T^N(U) \cap V \neq \varnothing\)) or totally transitive is undecidable. Unfortunately, the article has a few minor glitches and omissions that will demand extra work of the reader.
- The transitivity problem of Turing machines
- On relations between properties in transitive Turing machines
- On aperiodic reversible Turing machines (invited talk)
- Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
- On entropy and Turing machine with moving tape dynamical model
- One head machines from a symbolic approach
- On topological dynamics of Turing machines
- On the presence of periodic configurations in Turing machines and in counter machines.
- scientific article; zbMATH DE number 1738660
- Computability of the entropy of one-tape Turing machines
- A characterization of substitutive sequences using return words
- A small minimal aperiodic reversible Turing machine
- An Introduction to Symbolic Dynamics and Coding
- Beyond primitivity for one-dimensional substitution subshifts and tiling spaces
- Computability of the entropy of one-tape Turing machines
- Devaney's chaos or 2-scattering implies Li-Yorke's chaos
- Eigenfunctions for substitution tiling systems
- scientific article; zbMATH DE number 44378 (Why is no real title available?)
- scientific article; zbMATH DE number 124865 (Why is no real title available?)
- Mixing properties in coded systems
- On entropy and Turing machine with moving tape dynamical model
- On immortal configurations in Turing machines
- On the presence of periodic configurations in Turing machines and in counter machines.
- On topological dynamics of Turing machines
- One head machines from a symbolic approach
- Periodicity and Immortality in Reversible Computing
- Some undecidable problems about the trace-subshift associated to a Turing machine
- Substitution dynamical systems : algebraic characterization of eigenvalues
- Symbolic discrepancy and self-similar dynamics.
- The spectrum of dynamical systems arising from substitutions of constant length
- The transitivity problem of Turing machines
- The undecidability of the Turing machine immortality problem
- Topological mixing for substitutions on two letters
- Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable
- Zigzags in Turing Machines
This page was built for publication: Topological mixing notions on Turing machine dynamical systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672276)
