Abstract

Reversibility is equivalent to surjectivity within Turing machine topological systems. Although reversibility is a decidable property in Turing machines, a proper reverse Turing machine does not exist in the standard Turing model. Traditional solutions to this problem imply reducing the speed of the reversible Turing machine, therefore affecting its dynamics. Also, traces of topological dynamical systems of Turing machines can be surjective when the original Turing machine is not. A solution is a reversible Turing machine, considering a shift in the tape depending on the actual state, and also it is proven that surjectivity is undecidable for Turing machine subshifts only when the radius is 0.