A Binary Complete and Aperiodic Turing Machine
Pablo Concha-Vega and Rodrigo Torres-Avilés
Turing machines have been studied as dynamical systems for more than two decades, first formalized by Kůrka, proposing a topological dynamical system named Turing machine with moving tape (TMT). It was conjectured that every TMT has at least one periodic point. Nowadays, there are several examples of aperiodic Turing machines, disproving Kůrka’s conjecture. Moreover, one of these machines, named SMART, has other interesting properties like reversibility, completeness, topological minimality, among others. This machine has four states and works over an alphabet of three symbols. In this research, we study the dynamical properties of BinSmart, a 2-symbols reconstruction of the main dynamic of SMART machine. This machine results to be aperiodic, topologically minimal (therefore transitive) but not time-symmetric, as it is not a direct translation of the original machine. We also prove that its t-shift is a primitive substitution.
Keywords: Symbolic systems, topological dynamics, turing machines, subshifts, minimality, aperiodicity, substitution