The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible-its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retainillg their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, thereby avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), thereby restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy o f the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation. The usual digital computer program frequently performs operations that seem to throw away information about the computer's history, leaving the machine in a state whose immediate predecessor is ambiguous. Such operations include erasure or overwriting of data, and entry into a portion of the program addressed by several different transfer instructions. In other words, the typical computer is logically irreversible -its transition function (the partial function that maps each whole-machine state onto its successor, if the state has a successor) lacks a single-valued inverse. Landauer [ I ] has posed the question of whether logical irreversibility is an unavoidable feature of useful computers, arguing that it is, and has demonstrated the physical and philosophical importance of this question by showing that whenever a physical computer throws away information about its previous state it must generate a corresponding amount of entropy. Therefore, a computer must dissipate at least kTln 2 of energy (about 3 X 10"' joule at room temperature) for each bit of information it erases or otherwise throws away. An irreversible computer can always be made reversible by having it save all the information it would otherwise throw away. For example, the machine might be given an extra tape (initially blank) on which it could record each operation as it was being performed, in sufficient detail that the preceding state would be uniquely determined by the present state and the last record on the tape. However, as Landauer pointed out, this would merely postpone the problem of throwing away unwanted information, since the tape would have to be erased before it could be reused. It is therefore reasonable to demand of a useful reversible computer that, if it halts, it should have erased all its intermediate results, leaving behind only the desired output and the originally furnished input. (The machine must be allowed to save its input-otherwise it could not be reversible and still carry out computations in which the input was not uniquely determined by the output.) We will show that general-purpose reversible computers (Turing machines) satisfying these requirements indeed exist, and that they need not be much more complicated than the irreversible computers on which they are patterned. Computations on a reversible computer take about twice as many steps as on an ordinary one and may require a large amount of temporary storage. Before proceeding with the formal demonstration, the argument will be carried through at the present heuristic level. the auspices of the US. Atomic Energy Commission while the author was employed *Much of the work on physical reversibility reported in this paper was done under by the Argonne National Lsboratory, Argonne, Illinois. 525 We begin with the reversible but untidy computer mentioned earlier, which has produced, and failed to erase, a long history of its activity. Now, a tape full of random data cannot be erased except by an irreversible process: however, the history tape is not random-there exists a subtle mutual redundancy between it and the machine that produced it, which may be exploited to erase it reversibly. For example, if at the end of the computation a new stage of computation were begun using the inverse of the original transition function, the machine would begin carrying out the entire computation backward, eventually returning the history tape to its original blank condition [2]. Since the forward computation was deterministic and reversible, the backward stage would be also. Unfortunately, the backward stage would transform the output back into the original input, rendering the overall computation completely useless. Destruction of the desired output can be prevented simply by making an extra copy of it on a separate tape, after the forward stage, but before the backward stage. During this copying operation (which can be done reversibly if the tape used for the copy is initially blank), the recording of the history tape is suspended. The backward stage will then destroy only the original and not the copy. At the end of the comiputation, the computer will contain the (reconstructed) original input plus the intact copy of the output; all other storage will have been restored to its original blank condition. Even though no history remains, the computation is reversible and deterministic, because each of its stages has been so. One disadvantage of the reversible machine would appear to be the large amount of temporary storage needed for the history-for a v-step first stage, v records of history would have to be written. In a later section it will be argued that by performing a job in many stages rather than just three, the required amount of temporary storage can often be greatly reduced. The final section discusses the possibility of reversible physical computers, capable of dissipating less than kT of energy per step, using examples from the biochemical apparatus of the genetic code. This section formalizes the argument of the preceding section by showing that, given an ordinary Turing machine S, one can construczt a reversible three-tape Turing machine R, which emulates S on any standard input, and which leaves behind, at the end of its computation, only that input and the desired output. The R machine's computation proceeds by three stages as described above, the third stage serving to dispose of the history produced by the first. The remainder of this section may be skipped by those uninterested in the details of the proof. 526 The ordinary type of one-tape Turing machine [3] consists of a control unit, a readlwrite head, and an infinite tape divided into squares. Its behavior is governed by a finite set of transition formulas (commonly called quintuples) of the read-write-shift type. The quintuples have the form A T --z T' cr A ' , (1) meaning that if the control unit is in state A and the head scans the tape symbol T , the head will first write T' in place of T ; then it will shift left one square, right one square, or remain where it is, according to the value of w(-, +, or 0, respectively); finally the control unit will revert to state A ' . In the usual generalization to n-tape machines, T , T ' , and (T are all n-tuples within the quintuple. Each quintuple defines a (partial) one-to-one mapping of the present whole-machine state (Le., tape contents, head positions, and control state) onto its successor and, as such, is deterministic and reversible. Therefore a Turing machine will be deterministic if and only if its quintuples have non-overlapping domains, and will be reversible if and only if they have non-overlapping ranges. The former is customarily guaranteed by requiring that the portion to the left of the arrow be different for each quintuple. On the other hand, the usual Turing machine is not reversible. In making a Turing machine reversible, we will need to add transitions that closely resemble the inverses of the transitions it already has. However, because the write and shift operations do not commute, the inverse of a read-write-shift quintuple, though it exists, is of a different type; namely, shift-read-write. In constructing a reversible machine it is necessary to include quintuples of both types, or else to use a formalism in which transitions and their inverses have the same form. Here the latter approach is taken -the reversible machine will use a simpler type of transition formula in which, during a given transition, each tape is subjected to a read-write or to a shift operation but no tape is subjected to both. DeJnition: A quadruple (for an n-tape Turing machine having one head per tape) is an expression of the form where A and A' are positive integers (denoting internal states of the control unit before and after the transition, respectively); each t, may be either a positive integer denoting a symbol that must be read on the kth tape or a solidus ( / ) , indicating that the kth tape is not read during the transition; each t,' is either a positive integer denoting the symbol to be written on the kth tape or a member of the set (--, 0, +) denoting a left, null, or right shift of the kth tape head. t k = / . Thus the machine writes on a tape if and only if it has just read it, and shifts a tape only if it has not just read it. Like quintuples, quadruples define mappings of the whole-machine state which are one-to-one. Any readwrite-shift quintuple can be split into a read-write and a shift, both expressible as quadruples. For example, the quintuple (1) is equivalent to the pair of quadruples where A" is a new control-unit state different from A and A ' . When several quintuples are so split, a different connecting state A" must be used for each, to avoid introducing indeterminacy. Quadruples have the following additional important properties, which can be verified by inspection. Let be two n-tape quadruples. 1 ) a and p are mutually inverse (define inverse mappings of the whole-machine state) if and only if A = B' and B = A ' and, for every k , either ( t , = 11, = / and t,' = -14,') or (tk # / and t,' = 14, and t , = u,'). The inverse of a quadruple, in other words, is obtained by interchanging the initial control state with the final, the read tape symbols with the written, and changing the signs of all the shifts. 2 ) The domains of a and p overlap if and only if A = B and, for every k, ( t , = j or ulC = / or t, = 14,). Nonoverlapping of the domains requires a differing initial control state or a differing scanned symbol on some tape read by both quadruples. 3 ) The ranges of a and p overlap if and only if A' = B' and, for every k , ( t , = I or u, = I or t,' = u,'). The property is analogous to the previous one, but depends on the final control state and the written tape symbols. A reversible, deterministic n-tape Turing machine may now be defined as a finite set of n-tape quadruples, no two of which overlap either in domain or range. We now wish to show that such machines can be made to emulate ordinary (irreversible) Turing machines. It is convenient to impose on the machines to be emulated certain format-standardization requirements, which, however, do not significantly limit their computing power [ 4 ] . Definition: An input or output is said to be standard when it is on otherwise blank tape and contains no embedded blanks, when the tape head scans the blank square immediately to the left of it, and when it includes only letters belonging to the tape alphabet of the machine scanning it. and control states A , and A, appear in no other quintuple. These two are thus the first and last executed respectively in any terminating computation on a standard input. The letter b represents a blank. The phrase "machine M, given standard input string I , computes standard output string P" will be abbreviated M: I -+ P. For an n-tape machine this will become M: (Il; I,; . . '; I,) -+ ( P , ; P,; ' . .; P,,), where I, and P, are the standard input and the standard output on the kth tape. A blank tape will be abbreviated B . The main theorem can now be stated: Theorem: For every standard one-tape Turing machine S, there exists a three-tape reversible, deterministic Turing machine R such that if I and P are strings on the alphabet of S, containing no embedded blanks, then S halts on I if and only if R halts on ( I ; B ; B ) , and S: I -+ P if and only ifR: (I; B ; R ) -+ (I; B ; P ) . Furthermore, if S has f control states, N quintuples and a tape alphabet of z letters, including the blank, R will have 2f+ 2 N + 4 states, 4 N + 2z + 3 quadruples and tape alphabets of z , N + 1 , and z letters, respectively. Finally, if in a particular computation S requires u steps and uses s squares of tape, producing an output of length A, then R will require 4v + 4A + 5 steps, and use s, u + 1, and A + 2 squares on its three tapes, respectively. (It will later be argued that where u>> s, the total space requirement can be reduced to less than 2 6 . ) Proofi To construct the machine R we begin by arrangEach quintuple is now broken into a pair of quadruples ing the N quintuples of S in some order with the stanas described earlier. The mth quintuple becomes dard quintuples first and last: The newly added states A,,!' are different from the old states and from each other: each A' appears in only one (9) pair of quadruples. Table 1 Structure and operation of a three-tape reversible Turing machine. The computation proceeds in three stages using different sets of quadruples and control states, linkage occurring through states A, and C, , . On the right the contents of the tapes are shown symbolically at the beginning and end of each stage. The underbar denotes the posltlon of the head. The initial state is A and, for a terminating computation, C , is the final state. Contents o j tape  Working History
¶ ¶ -Bennet's classic paper REF studied the notion of a reversible Turing machine.
Logical reversibility of computation
Ibm Journal of Research and Development
Computer Science