Skip to main content
edited tags
Link
domotorp
  • 18.7k
  • 3
  • 57
  • 125
Source Link

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}?