2 edited tags
1

# reversible Turing machines

Hello, Let T be a Turing machine such that

1) it operates on the alphabet {0,1},

2) its set of states is A

3) the language it accepts is $L$ .

Does there exists a Turing machine S which also operates on the alphabet {0,1} and such that the language it accepts is L (the set of states might be different though) and such that, crucially, S is reversible?

By reversible I mean "the computational paths of S are disjoint". More precisely, the transition table of S gives rise to a map $K_S: \text{Tapes}\times B \to \text{Tapes} \times B$, where Tapes is the subset of the infinite product $\{0,1\}^Z$ consisting of those sequences which have a finite number of 1's, and B is the set of states of S. S is reversible iff, by definition, $K_S$ is injective on the set $$\bigcup_{i=0}^\infty K_S^{i}(\text{Tapes}\times \{Initial \} ),$$ where $Initial\in B$ is the initial state of S.

If the answer to the above question is "no" then what if we allow S to operate on an alphabet which is larger then {0,1}?