by A field guide to entropy, information, and computation
The bit is the answer to a yes-or-no question. Forty years of mid-century thinking turned that into entropy, communication, compression, error correction, and computation itself. Six interactive visualizations of the central ideas, plus the people who built them.
tags: Shannon, Von Neumann, Hamming, Turing, entropy, information, computation, Huffman, Maxwell, Wolfram, scientific, interactive
BELL LABS · INSTITUTE FOR ADVANCED STUDY · LOS ALAMOS · 1937 - 2001
Three minds - Shannon, von Neumann, Hamming - and the working culture that produced the bit, the stored-program computer, error-correcting codes, the Monte Carlo method, the channel-coding theorem, the implosion lens, and the hydrogen-bomb calculation. Twenty-five years inside the room.
CLAUDE E. SHANNON
1916 - 2001
Bell Labs · MIT
JOHN VON NEUMANN
1903 - 1957
IAS · Los Alamos
RICHARD W. HAMMING
1915 - 1998
Bell Labs · Los Alamos · NPS
H=−∑pi log pi
A bit is the answer to a yes-or-no question. That is the whole technology of the modern world.
What follows is a hands-on tour through the four pieces of mid-century thought that turned that one fact into the digital civilisation: entropy (how much surprise is in a message), information (how to send it through noise), error correction (how to fix it when noise wins), and computation (what can be done with it, once received). Most of these sliders, sliders, and grids are doing the actual math behind the scene. None of them are simulations of the math.
The page closes with twelve people who did this work, an institutional map of where, and an honest table of how each of them worked the hours.
Shannon’s 1948 paper begins by defining a quantity, H, that measures how much information a source produces. The unit is the bit - a word coined by John Tukey two years earlier in a Bell Labs memo. Drag the sliders. Watch H change. Note that maximum entropy is uniform (every symbol equally likely) and zero entropy is certainty (one symbol, always).
Drag the bars. Each bar is the probability of one symbol. The entropy H is the average number of yes/no questions you’d need to identify the symbol of the source - the average surprise. Maximum at uniform; zero at certainty.
The source-coding theorem (Shannon, 1948): a source with entropy H bits/symbol cannot be compressed losslessly to fewer than H bits per symbol on average. Above H, you can. Below H, you can not. Modern compression (gzip, JPEG, MP3, FLAC) lives within a few percent of this bound. Spiked distributions compress almost to nothing. Uniform ones not at all.
Shannon’s definition was lifted, deliberately, from statistical mechanics. Boltzmann’s thermodynamic entropy is the same mathematical object. Von Neumann advised Shannon to use the word for two reasons: first, it was already correct; second, "no one knows what entropy really is, so in a debate you will always have the advantage."
In 1867, James Clerk Maxwell imagined a tiny intelligent being that sorted fast molecules from slow ones at a gate, lowering the entropy of a gas without using any energy. The Second Law appeared to be violated. The puzzle stood for nearly a century.
James Clerk Maxwell’s thought experiment: a tiny demon stationed at a gate between two chambers, deciding which molecules to pass. Fast molecules accumulate on one side; slow ones on the other. A temperature gradient appears spontaneously. The Second Law - entropy never decreases - appears to be violated. The resolution took eighty years and is the reason your laptop has a fan.
Landauer’s principle (1961): erasing one bit of information from any physical system at temperature T must dissipate at least kT ln 2 joules of heat. Bennett (1982) showed that the demon’s sorting is reversible - no entropy cost - until it has to forget what it’s seen so it can keep working. The act of erasure pays back, exactly, the entropy the sorting saved. The Second Law is preserved. Pressing “erase memory” above is a free operation in our simulator only because we’re cheating thermodynamics. Your laptop is not.
Léo Szilárd noticed in 1929 that the demon must use information about the molecules; Rolf Landauer proved in 1961 that erasing one bit of information must dissipate at least kT ln 2 joules of heat; Charles Bennett showed in 1982 that the whole loop - sort, gain knowledge, eventually forget - balances. The Second Law is preserved by the energy cost of forgetting. Your laptop fan exists for this reason.
A diagram on page 2 of Shannon’s 1948 paper. Source → Encoder → Noisy Channel → Decoder → Destination. It says that information has units, that the channel has a capacity, and that below that capacity perfect communication is achievable. It says nothing about how. The how took the next forty years.
Bell System Technical Journal, July & October 1948. The diagram that named the bit and made every transmission system that followed a rigorous engineering object instead of a rumour.
10110010110110101011001011011000H(p)CShannon’s noisy-channel coding theorem (1948): for any rate R < C, there exists a code that drives the error probability arbitrarily close to zero. Below capacity, perfect communication. Above capacity, no code can save you. He proved this. He did not say how to construct the code - that problem took the next forty years.
Shannon proved that a source with entropy H bits/symbol cannot be compressed losslessly to fewer than H bits per symbol on average. He did not say how. David Huffman, then a 25-year-old graduate student, found the construction in 1952 as the answer to a take-home exam. Paste any text below to watch it work.
Paste any text. The Huffman algorithm assigns short binary codes to common symbols and long codes to rare ones. The achieved bits-per-symbol approaches the source’s entropy H - Shannon’s theoretical lower bound.
| symbol | freq | p | −log₂ p | Huffman code |
|---|---|---|---|---|
| i | 4 | 0.364 | 1.46 | 11 |
| s | 4 | 0.364 | 1.46 | 0 |
| p | 2 | 0.182 | 2.46 | 101 |
| m | 1 | 0.091 | 3.46 | 100 |
100110011001110110111Huffman’s achieved length is between H and H+1 bits per symbol. ASCII would have used 8 bits per symbol; a fixed-length code for this alphabet would have used 2. Shannon’s theorem says you cannot do better than H, on average, without losing information.
Shannon’s noisy-channel coding theorem said that codes existed which could drive the error rate arbitrarily close to zero. He didn’t construct one. Richard Hamming did, two years later. Type four data bits. Flip any received bit. Watch the decoder find and correct it from the parity-check syndrome alone.
Four data bits become seven by adding three parity bits. Flip any single bit in transmission - the decoder finds the position and corrects it from the parity-check syndrome alone. No retransmission. Hamming codes are still in your laptop’s ECC memory and your phone’s flash.
(s4 s2 s1) = (0 0 0) = 0 → no error
Recovered data: 1011 - matches original
The trick: the parity bits are placed at positions 1, 2, 4 (powers of two). Each parity covers exactly the bits whose position has the corresponding binary digit set. So the failing parities binary-encode the position of the error. Genius. Hamming’s 1950 paper is two pages long.
Twelve years before Shannon, Alan Turing had defined what it means to compute. A read-write head, an infinite tape, a finite set of state transitions. Turing’s 1936 paper proved that this minimal machine can simulate any algorithm whatsoever - and that some problems admit no algorithm at all. Pick a program below and run it.
Alan Turing’s 1936 model of computation. A head reads one symbol, writes one symbol, moves left or right, changes state, repeats. Anything a modern computer can compute, this can compute - with proportionally more steps. Choose a program. Step through. Watch.
Add 1 to a binary number. Carry until you find a 0 (or the end).
| state | read | write | move | → state |
|---|---|---|---|---|
| goto-end | 0 | 0 | R | goto-end |
| goto-end | 1 | 1 | R | goto-end |
| goto-end | ␣ | ␣ | L | add |
| add | 0 | 1 | H | halt |
| add | 1 | 0 | L | add |
| add | ␣ | 1 | H | halt |
Turing’s 1936 result: there exist problems no such machine can solve - not because the machine is too slow, but because no procedure can. The Halting Problem is the canonical example: there is no algorithm that, given an arbitrary program and input, decides whether the program will halt. The diagonal proof is shorter than this caption.
How simple can a computer be and still be universal? In 2002 Stephen Wolfram conjectured that Rule 110 - an 8-bit rule applied to a row of cells, in parallel, over discrete time - is Turing-complete. Matthew Cook proved it in 2004. Eight bits of program. Three rows of cells. The whole computer.
Each cell looks at itself and its two neighbours, then turns on or off according to a single 8-bit rule. Time runs downward. Rule 110 is Turing-complete - you could build a compiler in this. With three rows of cells.
Class IV: complex, both stable and chaotic regions. Turing-complete (Cook, 2004).
Cook’s 2004 result: Rule 110, evolved from the right initial conditions, can simulate any Turing machine. Eight bits of rule, plus an infinite stripe of zeros and ones, are sufficient for universal computation. Wolfram conjectured this in 1985; it took nineteen years and a 40-page proof to verify.
Each of the previous sections is keyed to one or two people. Below: the twelve in one place, with their working method as a one-liner and the biography unfolded on click.
Twelve figures. Each spent decades at one or two institutions (Bell Labs, MIT, Cambridge, IAS, Los Alamos, Stanford, Cold Spring Harbor, Caltech). Each had a recognisable working method. Click any card.
METHODWorked alone, slowly, on whatever interested him. Built things in the basement. The famous papers were sitting on his desk for years before he agreed to publish.
Shannon’s 1937 master’s thesis showed that George Boole’s 1854 algebra could be implemented in electrical relays. Every digital computer rests on this. His 1948 papers in the Bell System Technical Journal defined the bit, the channel, the noisy-channel coding theorem, the source-coding theorem, and most of the technical vocabulary information engineers still use. He built Theseus, a maze-solving robotic mouse (the first public demonstration of machine learning), the Useless Machine, a robot juggler, three unicycles, and a flame-throwing trumpet. He did not reply to letters. He retired into Alzheimer’s in the late 1980s and never wrote a memoir.
Twelve figures × eight working principles (open door, long tenure, lunch table, hands-on prototype, technical report, notebook, important problem, slow reply). Every filled cell is keyed to a documented anecdote. Click any cell.
Twelve thinkers across the eight principles. Filled cell = strongly characteristic. Half-cell = some evidence. Empty = not their thing. Click any filled cell for the anecdote.
| Open Door | Long Tenure | Lunch Table | Hands-On | Tech Report | Notebook | Important Problem | Slow Reply | |
|---|---|---|---|---|---|---|---|---|
| Shannon | ||||||||
| von Neumann | ||||||||
| Turing | ||||||||
| Wiener | ||||||||
| Hamming | ||||||||
| Feynman | ||||||||
| Hopper | ||||||||
| McClintock | ||||||||
| Crick | ||||||||
| Tukey | ||||||||
| Minsky | ||||||||
| Knuth |
strong some none
The institutional habitat that produced the work: Bell Labs Murray Hill, IAS Princeton, Los Alamos, the Cavendish, MIT’s long corridors. Five things mid-century institutions got right.
What the three of them shared was not a research field. They shared a working culture: long lunches at a physics table, a corridor with the office doors open, a technical-report series with no review board, a chalkboard that was never wiped. Five things that mid-century scientific institutions got right and most modern ones do not.
Hamming\u2019s observation: the man with his door closed gets more work done today; the man with his door open gets better work done over a decade. Bell Labs Murray Hill was built on a long axis with offices on both sides; it was difficult to walk to lunch without being hailed three times. Friction was the design.
At Bell Labs, the physics table sat Shockley, Brattain, Bardeen, J. B. Johnson; the chemistry table sat McCall, Pfann, Slichter. Hamming ate at one, then the other, asking the same question for a week: what are the important problems in your field? He made himself unwelcome and was promoted. At Los Alamos the lunchroom seated Feynman, Fermi, Bethe, Teller, von Neumann together. At IAS, Einstein walked home with G\u00f6del.
Bell Labs ran an internal mimeograph series with no review board. You wrote it, the typing pool typed it, the drawing pool drew the figures, you handed it out to anyone who asked. Shannon\u2019s 1948 paper is technically a Bell System Technical Journal article, but the working version had been a Memo for File for years before that. Speed beat polish. Polish came later, if it came.
Bell Labs had a machine shop in the basement. So did MIT, where Shannon learned to make Theseus. Von Neumann\u2019s IAS team built the IAS computer themselves \u2014 he was the only scientist on the project who could not solder, and he learned. The thing you could build was the thing you really understood.
Shannon stayed at Bell Labs for fifteen years. Hamming for thirty. Von Neumann was at IAS for twenty-four. Nobody was on a 3-year grant cycle. Nobody had to publish to keep their salary. They were paid to think, with a long enough horizon to make compounding work.
Three of the twelve, on the same axis - Shannon, von Neumann, Hamming. Shannon and Hamming overlapped at Bell Labs (an office shared in 1947). Von Neumann and Hamming overlapped at Los Alamos. Von Neumann and Shannon overlapped at IAS for the entropy conversation, c. 1949.
Three lanes (Shannon, von Neumann, Hamming) plus the world events they lived through. Click any pin to read the event.
↑ click any dot
Seven moments where the three biographies are the same biography. Letters, shared offices, lunch tables, paper acknowledgments, and one mimeographed manuscript that should have stayed locked in a drawer.
Hamming arrived at Bell Labs in 1946. He was given an office to share with Shannon for what turned out to be the year information theory was finished. They worked at separate desks, mostly silent, occasionally arguing about coding. Shannon developed information theory; Hamming, looking at the same problem from the engineer’s side, developed error-correcting codes. Both papers came out within a year of each other. "Why of all the people in Bell Labs then were those the two who did it?" Hamming would ask. "It was in the atmosphere."
The three are companion pieces. Shannon’s 1952 talk taught Hamming what he wrote down badly in 1972 and brilliantly in 1986. Feynman’s Caltech lectures took the same instinct and put it in front of a freshman class. The bibliography is one corridor.
✦ memory · ☽ night · ∞ loops · ❧ margins · ◆ proof
a personal library in perpetual arrangement · MMXXVI