Publication | Closed Access
Logical Reversibility of Computation
3.6K
Citations
0
References
1973
Year
EngineeringComputational Model TheoryPushdown AutomatonComputational ComplexityFormal VerificationSymbolic ComputationGeneral ComputationsComputational LogicSecond StageUseful ComputationsComputing SystemsCompilersAbstract MachineComputer EngineeringComputer ScienceLogical ReversibilityTheory Of ComputingAutomated ReasoningFormal MethodsAsynchronous SystemsTuring MachineComputability Theory
General‑purpose computing automata are logically irreversible, but making them reversible at every step could enable thermodynamically reversible computers that dissipate far less than kT per logical step. The reversible automaton first mirrors the irreversible machine while storing all intermediate results, then prints the output, and finally retraces the computation to erase the stored intermediates, restoring the machine to its initial state except for the output, as demonstrated on a three‑tape Turing machine. The authors demonstrate that a logically reversible machine can perform general computations, producing the desired output while reconstructing the input and leaving no extraneous data, thereby preserving simplicity and computational power.
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 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 now-written 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 three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.