Topological mixing notions on Turing machine dynamical systems (Q2672276)

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.