Lecture
Reversible Turing machine ( English . Reversible Turing machine ) - is a Turing machine in which every possible operation is reversible . As a result, the computations it produces are reversible .
A method of construction will be described. The Turing machine, which is ordinarily the subject of much discussion, is essential here. That is, for a pair (q, s) consisting of a state q and the symbol at the position of the head on the tape (hereafter simply called the “symbol”) s. There is only one action. At the same time, if it is possible to determine which operation was performed by looking only at the state and symbol immediately after the operation, the Turing machine can move in the opposite direction. In other words, it is precisely a reversible Turing machine that “solves in the reverse direction”.
A little more formally (I usually use a 5-tuple for the formal description of a Turing machine, but here I use a modified 4-tuple for convenience).
.Any two rules that are not the same [q out of all the rules of the Turing machine 
and 
With a reversible Turing machine, all injective computable functions can be computed.
A Turing machine is called reversible, if it has no merging reachable situations, and completely reversible, if it has no merging situations at all. The question of the existence of a reversible and completely reversible Turing machine equivalent to a given Turing machine was considered by V. S. Chernyavsky. He called Turing machines equivalent with respect to an alphabet 
if, having started work from the same initial situation in the alphabet m, they give the same final situation whenever one of them gives some final situation.
V. S. Chernyavsky proved that for every Turing machine T in the alphabet there exists a reversible Turing machine equivalent to machine T with respect to the alphabet ; for every Turing machine T there exists a machine equivalent to it with respect to its alphabet that is a composition of three completely reversible machines.
We shall call Turing machines completely equivalent with respect to the alphabet if, having started work from the same q1-situation in the alphabet , they give the same final situation whenever one of them gives some final situation. It is obvious that if machines are completely equivalent with respect to the alphabet , then they are equivalent with respect to that alphabet.
Theorem 1. For every Turing machine T in the alphabet one can construct a completely reversible machine T-1 such that for any q1-situations C1 and final situation C0 of machine T, the situation C0 is reachable from -C1 in machine T if and only if the situation C1 is reachable from C0 in machine T-1.
Theorem 2. For every Turing machine T in the alphabet one can construct a completely reversible machine T*, completely equivalent to machine T with respect to the alphabet .
Theorem 2 is a strengthening of the above results of V. S. Chernyavsky.
The main features of the proof of Theorems 1 and 2 are as follows. From the given machine T in the alphabet , an auxiliary machine T4 is constructed in the same alphabet, completely equivalent to machine T with respect to and possessing the following properties:
a) all states are one-sided, and no more than two instructions may have identical right-hand sides;
b) every q1-situation is elementarily unreachable, and every q1-situation to which machine T4 is applicable is non-solitary;
c) every situation to which machine T4 is applicable is either elementarily unreachable, or multiple, or non-solitary;
From property a) of machine T4 it follows that in machine T4 every situation is reachable from no more than two situations. For each pair of instructions of machine T4 with a common right-hand side, let us agree once and for all to call one of them a d-instruction, and the other a b-instruction. Let 
. then the expression 
means that in the sequence of situations 
the order in which the 
-instructions are used, where 
or 
, is as follows: 
1-instruction,
2-instruction, . . ., 
i -instruction.
Comments