reversible Turing machines - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:22:38Z http://mathoverflow.net/feeds/question/24083 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24083/reversible-turing-machines reversible Turing machines Ćukasz Grabowski 2010-05-10T11:47:12Z 2010-05-10T15:35:01Z <p>Hello, Let T be a Turing machine such that</p> <p>1) it operates on the alphabet {0,1}, </p> <p>2) its set of states is A</p> <p>3) the language it accepts is $L$ . </p> <p>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? </p> <p>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.</p> <p>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}?</p> http://mathoverflow.net/questions/24083/reversible-turing-machines/24086#24086 Answer by Joel David Hamkins for reversible Turing machines Joel David Hamkins 2010-05-10T12:02:39Z 2010-05-10T12:10:05Z <p>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$.</p> <p>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. </p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/24083/reversible-turing-machines/24087#24087 Answer by Antonio E. Porreca for reversible Turing machines Antonio E. Porreca 2010-05-10T12:04:22Z 2010-05-10T12:04:22Z <p>I think your map <i>K<sub>S</sub></i> also needs to take the position of the tape head as input, or am I missing something?</p> <p>The classic paper <a href="http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf" rel="nofollow">Logical reversibility of computation</a> by C.H. Bennett defines reversible Turing machines as</p> <blockquote> <p>a finite set of n-tape quadruples, no two of which overlap either in domain or range</p> </blockquote> <p>which should imply your notion of reversibility, assuming you allow an arbitrary alphabet instead of just &Sigma; = {0, 1}.</p> http://mathoverflow.net/questions/24083/reversible-turing-machines/24093#24093 Answer by supercooldave for reversible Turing machines supercooldave 2010-05-10T12:39:52Z 2010-05-10T12:39:52Z <p><a href="http://www.pps.jussieu.fr/~danos/" rel="nofollow">Vincent Danos</a> and <a href="http://www.comlab.ox.ac.uk/samson.abramsky/" rel="nofollow">Samson Abramsky</a> have done interesting work on reversible computation using different models of computation. Some interesting papers include <a href="http://www.pps.jussieu.fr/~danos/pdf/abstran.pdf" rel="nofollow">General Reversibility</a> and <a href="http://www.comlab.ox.ac.uk/files/339/revised.pdf" rel="nofollow">A Structural Approach to Reversible Computation</a>. The first is based on Milner's CCS; the second on Combinatorial Logic.</p> http://mathoverflow.net/questions/24083/reversible-turing-machines/24118#24118 Answer by Niall Murphy for reversible Turing machines Niall Murphy 2010-05-10T15:35:01Z 2010-05-10T15:35:01Z <p>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.</p> <hr> <p>[1] Kenichi Morita and Yoshikazu Yamaguchi, "A Universal Reversible Turing Machine" MCU2007</p>