Computation is a physical process when implemented on physical computers. As such, abstract logical operations within a computer can affect the external world in measurable ways. ## Landauer's principle Landauer's principle is the most well-known example of such a phenomenon. It states that a computer that erases a single bit of information must emit at least $k_BT \ln 2$ joules, usually as heat, to the environment. Intuitively: the entropy of the computer decreases when a bit is erased, and entropy cannot globally decrease (the second law of thermodynamics), so the difference must be emitted to the environment. This principle was introduced by Rolf Landauer in a 1961 paper titled [Irreversibility and Heat Generation in the Computing Process](https://ieeexplore.ieee.org/document/5392446). Erasing a bit in memory is not the only operation that incurs this energy cost. Consider an AND gate, which maps two inputs to a single output. The AND gate is logically irreversible, because it is not possible to reconstruct the inputs from the output; it computes a function that is not bijective. So the operation of an AND gate is guaranteed to generate entropy in the form of waste heat. In practice, the CMOS gates used in modern computers generate many orders of magnitude more waste heat than the Landauer limit, which only provides a lower bound. ## Reversible computing Current computers are limited by the considerable amount of heat that they dissipate, which necessitates extensive cooling infrastructure. The ultimate goal of reversible computing is to design computers that can dissipate arbitrarily little energy by circumventing Landauer's principle. I'm especially interested in reversible computing because it attempts to formalize the connection between thermodynamics and computation, which seems essential for the realization of [[Artificial life|artificial life]]. There are two properties that a reversible computer must possess: logical reversibility and thermodynamic reversibility. ### Logical reversibility A logically reversible [[Models of computation|model of computation]] moves through states according to a bijective transition function. That is, each state of the model has no more than one predecessor and no more than one successor. I say "no more than" because a state may be a halting state in either direction, and have no predecessor or successor. Such a theoretical machine can be stepped forwards or backwards freely, since no information is lost when the transition function is computed. A standard computer depends on circuits of logic gates, like AND and OR, that map two input bits to one output bit. These gates cannot be bijective, by the pigeonhole principle, so standard computers are logically irreversible. Additionally, models like the Turing machine and lambda calculus are irreversible by default; both allow transitions to states with multiple predecessors. Another way of saying this is that both models allow data to be erased. ### Thermodynamic reversibility A physical computer may be *thermodynamically reversible*. This means that the computer conserves energy, and produces no change in entropy, during its operation. By Landauer's principle, such a computer must be based on a logically reversible model of computation, because logically irreversible operations dissipate energy. Standard computers are thermodynamically irreversible, because transistors dissipate energy when they switch (among other reasons). To reiterate: thermodynamic reversibility requires logical reversibility, but not the other way around. I can easily simulate a logically reversible model of computation on a standard, thermodynamically irreversible computer.