Preprint 2015-17
Anahi Gajardo, Nicolas Ollinger, Rodrigo Torres:
The transitivity problem of Turing machine.
Abstract:
A Turing machine is topologically transitive if every partial configuration -that is a state, a head position, plus a finite portion of the tape- can reach any other partial configuration, provided that they are completed into proper configurations. We study topological transitivity in the dynamical system models of Turing machines with moving head, moving tape and for the trace-shift and we prove its undecidability. We further study minimality, the property of every configuration reaching every partial configuration.
