MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 325 characters in body

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?

1

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.