Abstract: The usual generalpurpose computing automaton (e.g., a Turing machine) is logically irreversible  its transition function lacks a singlevalued inverse Here it is shown that such machines may be made logically reversible at every step, while retaining 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 nowwritten output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of threetape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.
Landauer [1] 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 kT ln 2 of energy (about 3 ×10^{21} 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 generalpurpose 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.
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 computation, 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 nstep first stage, n 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.
The ordinary type of onetape Turing machine [3] consists of a control unit. a read/write head, and an infinite tape divided into squares. Its behavior is governed by a finite set of transition formulas (commonly called quintuples) of the readwrite shift type. The quintuples have the form

(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 s(, +, or 0, respectively); finally the control unit will revert to state A'. In the usual generalization to ntape machines, T, T', and s are all ntuples within the quintuple.
Each quintuple defines a (partial) onetoone mapping of the present wholemachine state (i.e., 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 nonoverlapping domains, and will be reversible if and only if they have nonoverlapping 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 readwriteshift quintuple, though it exists, is of a different type; namely, shiftreadwrite. 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 readwrite or to a shift operation but no tape is subjected to both.
Definition: A quadruple (for an ntape Turing machine having one head per tape) is an expression of the form

(2)

Like quintuples, quadruples define mappings of the wholemachine state which are onetoone. Any readwriteshift quintuple can be split into a readwrite and a shift, both expressible as quadruples. For example, the quintuple (1) is equivalent to the pair of quadruples

(3)



(4)

where A" is a new controlunit 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

(5)


and  

(6)

Definition: An input or output is said to he 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.
Definition: A standard Turing machine is a finite set of onetape quintuples

(1)

satisfying the following requirements:

(7)



(8)

The phrase "machine M, given standard input string 1, computes standard output string P'' will be abbreviated M: I®P. For an ntape machine this will become M: (I_{1}; I_{2}; . . .; I_{n}) ® (P_{1}; P_{2}; . . .; P_{n}), where I_{k}and P_{k} 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 onetape Tuning machine S, there exists a threetape 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 if R: (I: B; B) ® (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 + 2N + 4 states. 4N + 2z + 3 quadruples and tape alphabets of z, N + 1, and z letters, respectively. Finally. if in a particular computation S requires n steps and uses s squares of tape. producing an output of length l. then R will require 4n + 4l + 5 steps. and use s, n + 1. and l + 2 squares on its three tapes, respectively. (It will later be argued that where n >> s, the total space requirement can be reduced to less than 2 sqrt(ns).)
Proof: To construct the machine R we begin by arranging the N quintuples of S in some order with the standard quintuples first and last:
1) A_{1}b®b
+A_{2}.
. . . m) A_{j}T®T'sA_{k} . . . . N) A_{f}_{1}b®b 0 A_{f}, 
(9)

Each quintuple is now broken into a pair of quadruples as described earlier. The mth quintuple becomes
ì A_{j}T®T'A_{m}'  
í 
(10)


î A_{m}' / ® s A_{k} . 
The newly added states A_{m}' are different from the old states and from each other; each A' appears in only one pair of quadruples.
Two extra tapes are then added. one for the history and one for the duplicate copy of the output. The output (third ) tape is left blank and nullshifted for the present, but the history (second ) tape is used to record the index m as each transition pair is executed.
The mth pair of quadruples now has the form

(11)




Notice that the history (second) tape is out of phase with the other two  it is written on while they are being shifted and vice versa. This phasing is necessary to assure reversibility  it serves to capture the information that would otherwise be thrown away when the specific control state A_{m}' passes to the more general state A_{k}, The + shifting of the history tape assures that a blank square will always be ready to receive the next m value. If the computation of S does not halt, neither will that of R, and the machine will continue printing on the history tape indefinitely. On the other hand, if (on a standard input) S halts, R will eventually execute the Nth pair of quadruples, finding itself in state A_{f}, with the output in standard format on tape 1. The history head will be scanning the number N which it has just written at the extreme right end of the history on tape 2. Control then passes to the second stage of computation, which copies the output onto tape 3 (see Table 1). The control states for this stage are denoted by B's and are distinct from all the Atype control states. Notice that the copying process can be done reversibly without writing anything more on the history tape. This shows that the generation (or erasure) of a duplicate copy of data requires no throwing away of information.
The third stage undoes the work of the first and consists of the inverses of all firststage transitions with C's substituted for A's. In the final state C_{1}, the history tape is again blank and the other tapes contain the reconstructed input and the desired output.
As Table 1 shows, the total number of control states is 2N + 2f + 4, the number of quadruples 4N + 2z + 3, and the space and time requirements are as stated at the beginning of the proof. The nonoverlapping of the domains and ranges of all the quadruples assures determinism and reversibility of the machine R. In the first stage, the upper transitions of each pair do not overlap in their domains because of the postulated determinacy of the original Turing machine S, whose quintuples also began A_{j}T® . The ranges of the upper quadruples (as well as the domains of the lower ) are kept from overlapping by the uniqueness of the states A_{m}'. Finally, the ranges of the lower quadruples are saved from overlapping by the unique output in on the history tape. The state A_{f} causes no trouble, even though it occurs in both stage 1 and stage 2. because by the definition of the machine S it does not occur on the left in stage 1; similarly for state C_{f}. The nonoverlapping of the stage 2 quadruples can be verified by inspection, while the determinism and reversibility of stage 3 follow from those of stage 1.
In the case that S is a universal
Turing machine, R becomes a machine
for executing any computer program reversibly. For such a generalpurpose
machine it seems highly unlikely that we can avoid having to include the
input as part of the final output. However, there are many calculations
in which the output uniquely determines the input, and for such a problem
one might hope to build a specific reversible computer that would simply
map inputs onto outputs, erasing everything else. This is indeed possible,
provided we have access to an ordinary Turing machine which, given an output,
computes the corresponding input. Let S_{1}
be the (irreversible) Turing machine that computes the output from the
input and S_{2} be the one that computes
the input from the output. The reversible computation proceeds by seven
stages as shown in Table 2. of which the first three
employ a reversible form of the S_{1}
computer and, as in Table 1. serve to map the input
onto the input and output. Stage four interchanges input and output. Stages
five and seven use a reversible realization of the S_{2},
computer: stage five has the sole purpose of producing a history of the
S_{2}
computation (i.e., of the input from the output) which, after the extra
copy of the input has been erased in stage six, is used in stage seven
to destroy itself and the remaining copy of the input. while producing
only the desired output
We shall now return to the more usual situation, in which the input
must be saved because it is not a known, computable function of the output.
Performing a computation reversibly entails only a modest increase in computing
time and machine complexity; the main drawback of reversible computers
appears thus to be the large amount of temporary storage they require for
the history in any long, computebound job (i.e., one whose number of steps,
n,
greatly exceeds the number of squares of memory used. s). Fortunately,
the temporary storage requirement can be cut down by breaking the job into
a sequence of n segments, each one
of which would be performed and retraced (and the history tape thereby
erased and made ready for reuse) before proceeding to the next. Each segment
would leave on the working tape (tape 1) a restart dump that would be used
as the input of the next segment; but to preserve reversibility it would
also have to leave (on tape 3, say) a copy of its own input, which would
in most cases simply be the preceding restart dump. At the end of the computation
we would have, in addition to the original input and desired output, all
the
It thus appears that every job of computation can be done in a logically
reversible manner, without inordinate increases in machine complexity,
number of steps, unwanted output, or temporary storage capacity.
An obvious approach to the minimizing the energy dissipation is to design the computer so that it can operate near thermodynamic equilibrium. All moving parts, would then, at any instant. have nearthermal velocity, and the desired logical transitions would necessarily be accomplished by spontaneous thermally activated motion over free energy barriers not much higher than kT. At first sight this might seem impossible  in existing electronic computers. for example. even when a component being switched is itself nondissipative (e.g.. a magnetic core). the switching process depends on temporarily applying a strong external force to push the component irreversibly over a high free energy barrier. However, nature provides a beautiful example of a thermally activated "computer" in the biochemical apparatus responsible for the replication. transcription and translation of the genetic code [6]. Each of these processes involves a long, deterministic sequence of manipulations of coded information, quite analogous to a computation, and yet, so far as is known. each is simply a sequence of coupled. thermally activated chemical reactions. In biochemical systems. enzymes play the essential role of selectively lowering the activation barriers for the desired transitions while leaving high barriers to obstruct all undesired transitions those which in a computer would correspond to errors. Although the environment in which enzymes normally function is not at chemical equilibrium. Many enzymecatalyzed reactions are freely reversible. and one can find a set of equilibrium reactant concentrations at which both forward and reverse reactions occur equally rapidly. while competing uncatalyzed reactions have negligible rates. It is thus not unreasonable to postulate a thermally activated computer in which, at equilibrium, every logically allowed transition occurs equally often forward and backward. while illogical transitions hardly ever occur. In the following discussion chemical terminology will be used. without implying that thermally activated computers must be chemical systems.
The chemical realization of a logically reversible computation is a
chain of reactions. each coupled only to the preceding one and the following
one. It is helpful to think of the computing system as comprising a major
reactant (analogous to DNA) that encodes the logical state, and minor reactants
that react with the major one to change the logical state. Only one molecule
of the major reactant is present, but the minor reactants are all present
at definite concentrations. which may be manipulated to drive the computation
forward or backward. If the minor reactants are in equilibrium, and the
major reactant initially corresponds to the initial state of a nstep
computation, the system will begin a random walk through the chain of reactions,
and after about n^{2}
steps will briefly visit the final state. This does not deserve to be called
a computation; it would be legitimate to insist that the system proceed
through the chain of reactions with some positive drift velocity. and.
after sufficient time. have a high probability of being in the final state
(if the computation has one). The former requirement can be met by adjusting
the chemical potentials of the minor reactants so that each forward step
dissipates a little energy e;
the latter can be met by dissipating a trivial extra amount during the
last step. (If all steps had equal dissipation,
If we attempt to apply the preceding argument to a logically irreversible computer, we can see that here the reactions form a branching structure, with a main trunk corresponding to the desired computation path. and side branches corresponding to incorrect or "extraneous" reverse computations. The states on the side branches are valid predecessors of the final state but not valid successors of the initial state. A few such extraneous states would pose no problem  a small driving force would still suffice to push the system into the desired final state. Temporary backward excursions onto the side branches would occur, but would not lead to errors, contrary to what one might expect. Since no state of a deterministic computer can have more than one logical successor, the erroneously reversed operations would be corrected as soon as the computation proceeded forward again, and the desired path would be rejoined. The real problem comes from the enormous number of extraneous predecessors: typically they outnumber the states on the intended computation path by hundreds of orders of magnitude. This is because, in irreversibly programmed computations, one can usually proceed backward along an extraneous path for many steps, making further wrong choices along the way, before arriving at a state that has no predecessors.
If a thermally activated computer with many extraneous states is operated close to equilibrium. the system will spend only a minuscule fraction of its time on the desired path of computation. let alone in the desired final state. An acceptable computation rate requires 1) that finite (but timeconsuming) backward excursions be largely suppressed, and 2) that infinite ones be completely suppressed. This in turn means (roughly speaking) that the dissipation per step must exceed kT ln m. where m is the mean number of immediate predecessors 1) averaged over states near the intended path, or 2) averaged over all accessible states. whichever is greater. For a typical irreversible computer, which throws away about one bit per logical operation, m is approximately two, and thus kT ln 2 is as Landauer has argued [1], an approximate lower bound on the energy dissipation of such machines. For a logically reversible computer. however. m is exactly one by construction.
The biosynthesis and biodegradation of messenger RNA may be viewed as convenient examples of logically reversible and irreversible computation. respectively. Messenger RNA. a linear polymeric informational macromolecule like DNA, carries the genetic information from one or more genes of a DNA molecule. and serves to direct the synthesis of the proteins encoded by those genes. Messenger RNA is synthesized by the enzyme RNA polymerase in the presence of a doublestranded DNA molecule and a supply of RNA monomers (the four nucleotide pyrophosphates ATP, GTP, CTP, and UTP) [7]. The enzyme attaches to a specific site on the DNA molecule and moves along, sequentially incorporating the RNA monomers into a singlestranded RNA molecule whose nucleotide sequence exactly matches that of the DNA. The pyrophosphate groups are released into the surrounding solution as free pyrophosphate molecules. The enzyme may thus be compared to a simple tapecopying Turing machine that manufactures its output tape rather than merely writing on it. Tape copying is a logically reversible operation. and RNA polymerase is both thermodynamically and logically reversible. In the cellular environment the reaction is driven in the intended forward direction of RNA synthesis by other reactions. which maintain a low concentration of free pyrophosphate, relative to the concentrations of nucleotide pyrophosphates [8]. A high pyrophosphate concentration would drive the reaction backward. and the enzyme would carry out a sequencespecific degradation of the RNA. comparing each nucleotide with the corresponding DNA nucleotide before splitting it off. This process, which may be termed logically reversible erasure of RNA, does not normally occur in biological systems  instead, RNA is degraded by other enzymes. such as polynucleotide phosphorylase [9], in a logically irreversible manner (i.e.. without checking its sequence against DNA). Polynucleotide phosphorylase catalyzes the reaction of RNA with free phosphate (maintained at high concentration) to form nucleotide phosphate monomers. Like the polymerase reaction. this reaction is thermodynamically reversible: however, because of its logical irreversibility, a fourfold greater phosphate concentration is needed to drive it forward than would be required for a logically reversible phosphorolytic degradation. The extra driving force is necessary to suppress the undesired synthesis of nonsense RNA by random polymerization. In biological systems. apparently, the speed and flexibility of irreversible erasure outweigh its extra cost in free energy kT ln 4 per nucleotide in this case). Indeed, throughout the genetic apparatus, energy is dissipated at a rate of roughly 5 to 50 kT per step. while this is ten orders of magnitude lower than in an electronic computer. it is considerably higher than what would theoretically be possible if biochemical systems did not need to run at speeds close to the kinetic maximumpresumably to escape the harmful effects of radiation, uncatalyzed reactions, and competition from other organisms.
C. H. Bennett is located at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598.