12
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I'm voting to keep this question open because it was asked a long time ago, seems to have been answered satisfactorily, and I see no reason why anyone should seek closure unless they are on a deletion mission. $\endgroup$
    – Yemon Choi
    Commented Feb 23, 2019 at 23:44

4 Answers 4

Reset to default
5
$\begingroup$

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?

Improve this answer
$\endgroup$
11
  • $\begingroup$ I don't think this answers the OP's intended question: he would like a finite increase of the state space (or perhaps the alphabet as well) which allows this. You use the tape to track this, in a clearly unbounded manner. $\endgroup$
    – Jacques Carette
    Commented May 10, 2010 at 12:06
  • $\begingroup$ My solution has only a finite increase in the state space (since the universal machine has only finitely many states), and no increase in the alphabet. Of course, it does use more of the tape, and the computations will take longer time. But the OP may object that my computations are only reversible on the configurations that arise in normal computation, and not necessarily on all possible configurations. $\endgroup$
    – Joel David Hamkins
    Commented May 10, 2010 at 12:13
  • $\begingroup$ 1) My definition requires injectivy on the set $Y=\bigcup ...$, not on the whole set $\text{Tapes} \times B$. $Y$ is precisely the set of configurations which arise in the actual computation. 2) I insist on considering a Turing machine with just one tape. $\endgroup$
    – Łukasz Grabowski
    Commented May 10, 2010 at 19:41
  • 2
    $\begingroup$ Lukasz, in this case, my answer seems to meet all your requirements. I had in mind that my algorithm would use just one tape. In any case, Turing machines with one tape can easily simulate Turing machines with multiple tapes---these computational models are well-known to have equal power. $\endgroup$
    – Joel David Hamkins
    Commented May 10, 2010 at 23:11
  • $\begingroup$ Joel, I'm still unhappy, but I admit your answer answers my question :-). Let me informally say why I'm still unhappy. Suppose T' operates on {0,1,g}, where g is certain special symbol, but at the beginning T' is not given a tape with only 0's and the word written on it but rather a tape with a word written between two symbols g, and random entries elsewhere. Starting with the original T one can easily modify it and define T' in such a way that it ignores entries besides the two symbols g and so it accepts the word between two g's iff this word belongs to L. (TBC) $\endgroup$
    – Łukasz Grabowski
    Commented May 11, 2010 at 12:37
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

I think your map KS 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}.

Improve this answer
$\endgroup$
3
  • $\begingroup$ By the way, if I recall correctly, Bennet’s construction is very similar to what Joel David Hamkins suggests in his answer. $\endgroup$
    – Antonio E. Porreca
    Commented May 10, 2010 at 12:19
  • $\begingroup$ As to the position, I consider $\\{0,1\\}^Z$ to mean the set of functions from Z (i.e. integers) to {0,1}, so the position is automatically encoded. Unfortunately this paper gives an answer which is a Turing machine with more than one tape, which does not satisfy me. S should be a standard one-tape Turing machine. $\endgroup$
    – Łukasz Grabowski
    Commented May 10, 2010 at 19:46
  • $\begingroup$ Sorry, it should be "I consider {0,1}^Z..." $\endgroup$
    – Łukasz Grabowski
    Commented May 10, 2010 at 19:47
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link in the answer no longer works, but the paper V. Danos, J. Krivine, P. Sobociński: General reversibility can be found at DOI: 10.1016/j.entcs.2006.07.036. $\endgroup$
    – Martin Sleziak
    Commented Mar 17, 2023 at 16:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .