Reversible computing: Difference between revisions

Revision as of 23:01, 23 June 2023

Revision as of 23:32, 15 July 2023

Line 35:

An [[inverter (logic gate)|inverter]] (NOT) gate is logically reversible because it can be ''undone''. The NOT gate may however not be physically reversible, depending on its implementation.

The [[exclusive or]] (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, or alternatively, because information erasure is not reversible. However, a reversible version of the XOR gate—the [[controlled NOT gate]] (CNOT)—can be defined by preserving one of the inputs as a 2nd output. The three-input variant of the CNOT gate is called the [[Toffoli gate]]. It preserves two of its inputs ''a,b'' and replaces the third ''c'' by <math>c\oplus (a\cdot b)</math>. With <math>c=0</math>, this gives the AND function, and with <math>a\cdot b=1</math> this gives the NOT function. Because AND and NOT together is a [[functional completeness|functionalfunctionally complete]] set, the Toffoli gate is universal and can implement any [[Boolean function]] (if given enough initialized [[ancilla bit]]s).

Similarly, in the [[Turing machine]] model of computation, a reversible Turing machine is one whose transition function is invertible, so that each machine state has at most one predecessor.