Appendix A — Concepts
Every technical term the book uses, in plain language. Each entry lists the pages that use it.
Arrow of time
The difference between past and future that we observe in everyday life: eggs break but do not unbreak, and we remember yesterday but not tomorrow. It stands out because the fundamental laws of physics barely distinguish between the two directions of time.
Related: Entropy, Second law of thermodynamics
Bit
The word has two meanings that are kept apart. A bit is a binary digit: one place in a memory or a message that holds 0 or 1, so ten such places hold ten bits. It is also the everyday name of the unit of information, whose own name is the shannon (symbol Sh). Learning which of two equally likely answers is the true one gives one shannon; an answer that could be predicted gives less, and a certain one gives none. So ten binary digits carry at most ten shannons, and exactly ten only when every sequence is equally likely. Claude Shannon set out the measure in 1948: the logarithm to base 2 of the number of equally likely possibilities. Taken with the natural logarithm instead, the same information is measured in nats, and one shannon is \(\ln 2\) nat, about 0.693 nat. The shannon is the unit named in the standard IEC 80000-13:2025. Entropy in thermodynamics is \(k_B\) times the information in nats, which is why Landauer’s bound for erasing one bit, \(k_B T \ln 2\), carries the factor \(\ln 2\): it converts one shannon into nats.
Related: Landauer’s principle, Entropy
References: (Shannon 1948)
Closed timelike curve
A path through spacetime that returns to its own past. Such curves are not known to exist, but studying them has taught something about general relativity and quantum information. Following David Deutsch, a closed timelike curve is treated as a region of spacetime where nature must produce a consistent outcome: a fixed point of whatever process runs around the loop. Aaronson and Watrous showed in 2008 that, if such curves existed, quantum computers would be no more powerful than classical ones: both could solve exactly the problems that need a polynomial amount of memory (PSPACE).
Related: Arrow of time
References: (Deutsch 1991; Aaronson and Watrous 2008)
Entropy
A measure of how many microscopic arrangements of a system (its microstates) are compatible with what we observe at large scale (its macrostate). The more ways the parts can be arranged without changing how the whole looks, the higher the entropy. It grows with the logarithm of that number: the entropy is \(k_B\) times its natural logarithm, so doubling the number of arrangements adds \(k_B \ln 2\), however large the system. Thermodynamics measures the same quantity through heat: heat taken in reversibly at temperature \(T\), divided by \(T\), is the change in entropy.
Related: Second law of thermodynamics, Arrow of time, Bit
Landauer’s principle
Erasing one bit of information in surroundings at temperature \(T\) releases at least \(k_B T \ln 2\) of heat. Forgetting has a minimum physical cost. The bound was proposed by Rolf Landauer in 1961 and confirmed experimentally in 2012.
Related: Bit, Reversible computing, Maxwell’s demon
References: (Landauer 1961; Bérut et al. 2012)
Maxwell’s demon
A thought experiment devised by James Clerk Maxwell in 1867: a tiny being opens and closes a door between two boxes of gas, letting fast molecules go one way and slow ones the other. It seems to lower entropy for free. The accepted resolution is that the demon must record what it sees, and erasing that record eventually pays the entropy back.
Poincaré recurrence
A theorem of Henri Poincaré: any finite system comes arbitrarily close to its initial state after some very long but finite time. Taken statistically it is not a paradox, but it seems to violate the second law of thermodynamics, since the entropy of a gas would in time return near its starting value. The theorem leaves gravity out; with gravity, colliding particles can form black holes, which can quench the recurrence or change how long it takes.
Related: Second law of thermodynamics, Entropy, Arrow of time
References: (Dong and Stojkovic 2016)
Quantum speed limit
The shortest time in which a quantum system can evolve into a state fully distinguishable from the one it started in. Leonid Mandelstam and Igor Tamm bounded it by the spread of the system’s energy; Norman Margolus and Lev Levitin, in 1998, by its average energy above the lowest possible: the time is at least \(\pi\hbar / 2E\), with \(E\) measured from the ground state. Each step of a computation has to reach a distinguishable state, so the limit caps how many steps per second a computer with a given energy can take.
Related: Bit, Reversible computing
References: (Mandelstam and Tamm 1991; Margolus and Levitin 1998; Lloyd 2000)
Reversible computing
Computing without erasing information, so that every step can be run backward. Two meanings are kept apart. A computation is logically reversible when each state has only one possible predecessor, so the input can be recovered from the output; Charles Bennett showed in 1973 that a general-purpose computer can be made logically reversible at every step. It is thermodynamically reversible when it produces no entropy, a limit a real device approaches only by running ever more slowly. Logical reversibility removes the minimum cost that Landauer’s principle sets on erasure; it does not by itself remove the rest of the dissipation.
Related: Landauer’s principle, Bit
References: (Bennett 1973)
Second law of thermodynamics
In an isolated system, entropy does not decrease over time. It is a statistical law: a decrease is not forbidden, only overwhelmingly unlikely for systems with many parts.
Related: Entropy, Arrow of time, Maxwell’s demon
Szilard engine
The simplest case of Maxwell’s demon, studied by Leo Szilard in 1929: a box holding a single molecule, in thermal contact with a heat bath, and a partition that can be inserted and can slide along the box. With the partition inserted, the molecule pushes on it; if it moves the way it is pushed, it can lift a weight, and the most work this extracts is \(k_B T \ln 2\), drawn from the heat bath alone. Szilard argued that the second law is saved if the demon’s acquisition of knowledge, which side the molecule is on, comes with a compensating entropy cost.
Related: Maxwell’s demon, Landauer’s principle, Second law of thermodynamics
References: (Maroney 2009)
Turing machine
An abstract model of computation introduced by Alan Turing in 1936: a machine that reads and writes symbols on an unlimited tape, following a finite table of rules. Anything a modern computer can compute, a Turing machine can compute too, given enough time and tape.
Related: Bit
References: (Turing 1937)