Skip to main content
Engineering LibreTexts

7.5: Reversible computers

  • Page ID
    52423
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    In the previous section, we defined computation as a process that increases information and decreases uncertainty. But if uncertainty (i.e. entropy) decreases within the computer, entropy must increase outside the computer. This is an application of the second law of thermodynamics, which states that all physical systems can only increase entropy over time.

    Of all physical laws, the second law of thermodynamics is famous for defining the "arrow of time". The implication of the second law is that computation is irreversible, at least if the computation changes uncertainty.

    For example, let's consider a two input AND gate. If one of the inputs to the AND gate is a zero, then the information in the other input is thrown away. Thus, the total number of states decreases when the inputs propagate to the output of an AND gate. Consequently, entropy decreases, heat is dissipated and AND gates are not reversible.

    Screenshot 2021-05-27 at 15.04.52.png
    Figure \(\PageIndex{1}\): AND gates are not reversible. If the output is zero, the inputs cannot be reconstructed.

    The heat dissipated in the AND gate is calculated as follows. There are four possible input states. Assuming each is equi-probable the Shannon entropy is

    \[ H_{in} = -\log_{2} 1/4 = 2 \text{ bits} \nonumber \]

    There are two possible output states. The probability of the output X = 0 is ¾ and the probability of X = 1 is ¼.

    \[ H_{out} = -\frac{3}{4} \log_{2} 3/4 - \frac{1}{4}\log_{2}1/4 \approx 0.811 \text{ bits} \nonumber \]

    Thus,

    \[ \Delta E = -k_{B} T\ln(2)\Delta H \approx 3.4\times 10^{-21} J \nonumber \]

    But what if we designed a gate that did not throw away states during the computation? Such a system would be reversible, and more importantly it would not need to dissipate energy.

    In fact, several reversible logic elements have been proposed. Perhaps the best known irreversible computer is the billiard ball computer pioneered by Fredkin.

    An example of a billiard ball logic gate is shown in Figure \(\PageIndex{2}\). Billiard balls are fired into the logic gate from positions A and B. If there is a collision, the balls are deflected to positions W and Z. If one ball is absent, however, an output at either X or Y is generated. We also need to assume that the balls obey the laws of classical mechanics; there is no friction and the collisions are perfectly elastic. Note that the number of states in a billiard ball logic elements does not change – the billiard balls are neither created nor destroyed.

    Screenshot 2021-05-27 at 15.09.54.png
    Figure \(\PageIndex{2}\): A two ball collision gate. After Feynman, Lectures on Computation. Editors A.J.G. Hey and R.W. Allen, Addison-Wesley 1996.

    More complex devices are possible by adding "redirection gates" (walls). For example, Figure \(\PageIndex{3}\) shows a switch made from collision and redirection gates.

    Screenshot 2021-05-27 at 15.11.11.png
    Figure \(\PageIndex{3}\): A billiard ball switch. After Feynman, Lectures on Computation. Editors A.J.G. Hey and R.W. Allen, Addison-Wesley 1996.

    But given that many logic gates such as the AND gate are inherently non-reversible, the question arises: Can an arbitrary algorithm be implemented entirely from reversible elements? The answer is yes. Reversible computers can be constructed entirely of a fundamental reversible element known as the Fredkin gate, shown in Figure \(\PageIndex{3}\).

    Screenshot 2021-05-27 at 15.12.17.png
    Figure \(\PageIndex{4}\): The symbol for the Fredkin gate. A is unchanged. If A = 0 then B and C switch. If A = 1 then B and C remain unchanged. All logic elements may be formulated from reversible Fredkin gates. After Feynman, Lectures on Computation. Editors A.J.G. Hey and R.W. Allen, Addison-Wesley 1996.

    An implementation of a Fredkin gate with billiard balls is shown in Figure \(\PageIndex{4}\).

    Screenshot 2021-05-27 at 15.13.13.png
    Figure \(\PageIndex{5}\): A Fredkin gate constructed from four billiard ball switches. After Feynman, Lectures on Computation. Editors A.J.G. Hey and R.W. Allen, Addison-Wesley 1996.

    7.5: Reversible computers is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by LibreTexts.