Logical Reversibility of Computation

摘要: The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks single-valued inverse. Here it shown that such machines may he made reversible at every step, while retainillg their simplicity and ability to do general computations. This result of great physical interest because makes plausible the existence thermodynamically computers which could perform useful computations speed dissipating considerably less than kT energy per logical step. In first stage computation parallels corresponding irreversible automaton, except saves all intermediate results, there by avoiding operation erasure. second consists printing out desired output. third then reversibly disposes undesired results retracing steps in backward order (a process only possible has been carried reversibly), restoring machine (except for now-written output tape) original condition. final configuration thus contains reconstructed copy input, but no other data. foregoing are demonstrated explicitly using type three-tape machine. biosynthesis messenger RNA discussed as example computation.