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



reversible Turing machines
Using the method of the universal Turing machine, consider the Turing machine $S$ that on input $x$ simulates the computation of $T$ on $x$, and keeps track of the entire computation history. That is, $S$ writes down on the tape complete descriptions (tape contents, state, head position) of each successive step of the computation of $T$ on $x$. If eventually $S$ finds that $T$ accepts or rejects $x$, then $S$ should also accept or reject $x$.


This computation is reversible, since at any stage of the computation of $S$ on $x$, we can easily read off $x$ from the description of the first configuration, and so we know how $S$ started and therefore how we got to where we are. 


Another way to do it would be the following: using a pairing function, regard the tape as two tapes, and then on input $x$, make a copy of $x$ on one of the tapes, and then with each step of simulated computation increment a counter on this tape (by adding one more $1$). This process leads to a reversible computation, since from any stage in the computation we can tell what the input was, and how many simulated steps have been performed. So we know where the computation came from.


These computation are reversible in the weaker sense that they can be reversed from the configurations that actually arise in computation, whereas your definition seems to require reversibility on all possible finite confgurations, even if these would not arise during an actual computation. Is that really what you want?


