reversible Turing machines - MathOverflow

reversible Turing machines

2010-05-10T11:47:12Z

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

Answer by Joel David Hamkins for reversible Turing machines

2010-05-10T12:02:39Z

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?

Answer by Antonio E. Porreca for reversible Turing machines

2010-05-10T12:04:22Z

I think your map K_S also needs to take the position of the tape head as input, or am I missing something?

The classic paper Logical reversibility of computation by C.H. Bennett defines reversible Turing machines as

a finite set of n-tape quadruples, no two of which overlap either in domain or range

which should imply your notion of reversibility, assuming you allow an arbitrary alphabet instead of just Σ = {0, 1}.

Answer by supercooldave for reversible Turing machines

2010-05-10T12:39:52Z

Vincent Danos and Samson Abramsky have done interesting work on reversible computation using different models of computation. Some interesting papers include General Reversibility and A Structural Approach to Reversible Computation. The first is based on Milner's CCS; the second on Combinatorial Logic.

Answer by Niall Murphy for reversible Turing machines

2010-05-10T15:35:01Z

Well there are universal reversible Turing machines (RTMs), for example [1]. So you can simulate T with a universal RTM. The resulting machine would be reversible and accept L.

[1] Kenichi Morita and Yoshikazu Yamaguchi, "A Universal Reversible Turing Machine" MCU2007