Bits, orders of magnitude, state spaces — and why testing shows presence, not absence.
This is selfie's synopsis: a regular expression that says exactly how selfie may be invoked. Braces mean any number of, brackets mean optional, the bar means or. We learn to read it properly in week 4.
For today: -c selfie.c compiles selfie's own source. Watch what it prints about itself.
Left. From one thing to every atom there is — the whole physical world in eighty steps, each one ten times the last.
The wall. No number of steps crosses it. Infinity is not the far end of the line; it is what the line never reaches.
Right. Past the wall, endlessness comes in sizes: one counts every notation, the other every meaning — and is strictly bigger.
A million seconds ago you had not yet packed for today. A billion seconds ago you were a child, or not yet born. A trillion seconds ago somebody was painting the walls of the Chauvet cave.
Never accept a number you cannot picture. Find the anchor — a fortnight, a career, an ice age — or admit you are repeating the number, not reading it.
| prefix | factor | bytes · how much it holds | hertz · how often it happens |
|---|---|---|---|
| kilo | 103 | KB — a long paragraph | kHz — the top of human hearing, 20 kHz |
| mega | 106 | MB — a novel | MHz — the first IBM PC, 4.77 MHz, 1981 |
| giga | 109 | GB — a thousand novels | GHz — this laptop; Wi-Fi at 2.4 |
| tera | 1012 | TB — a million novels | THz — infrared light |
A byte is eight bits — one keystroke. A hertz is one beat per second. The left column counts things, the right counts events, and the prefixes do not care which.
At 1 GHz a beat lasts a billionth of a second, and light gets 30 cm in that time. Grace Hopper handed those 30 cm out as lengths of wire, so a room could feel why a signal cannot cross a desk and return inside one beat.
| base 10 | base 2 | gap | |
|---|---|---|---|
| kilo | KB = 103 | KiB = 210 = 1,024 | +2.4% |
| mega | MB = 106 | MiB = 220 | +4.9% |
| giga | GB = 109 | GiB = 230 | +7.4% |
| tera | TB = 1012 | TiB = 240 | +10.0% |
Memory is addressed with bits, so its natural steps are powers of two — and 210 lands so close to 1,000 that the prefix was simply borrowed. Memory comes in powers of two; disks and networks in powers of ten. A "1 TB" drive holds 1012 bytes and shows up as 931 GiB.
One notation, two meanings, and nothing in the notation to tell you which you were handed. Keep hold of that. The rest of the semester is about that gap.
Add a bit and you don't add states. You double them.
Ten bits: a thousand states. Twenty: a million. Thirty: a billion.
Doubling is the most underestimated operation in human reasoning — and the entire engine of computing.
How many bits does it take to have more states than the universe has atoms?
37 bytes to beat every photon, about 1089.
Written out in decimal, that number has about 20.7 billion digits. At 3,000 digits a page: 6.9 million pages. Bound into 500-page books: 13,800 volumes — some 400 metres of shelf.
That shelf does not hold the phone's states. It holds the number of them, written down once.
Every app you will ever install, every photo you will ever take, and every bug you will ever hit is one point in this space.
RISC-U has 4 GB of byte-addressed memory: 235 bits, so 234,359,738,368 states — a number with 10.3 billion decimal digits. Selfie, the program that runs on it, is 12,394 lines. One person can read the program to the end. Nobody can inspect the machine.
Test a billion states per second, starting at the Big Bang, and by now you would have checked about 288 of them. Out of 268,719,476,736.
The fraction is not small. It is indistinguishable from zero.
Testing shows the presence, not the absence of bugs.Edsger W. Dijkstra, 1969
Certainty by inspection. You will never check your system exhaustively — not with more testers, not with faster machines, not ever.
Every symphony not yet written, every protein not yet folded, every proof not yet found, every program not yet imagined — all of them are already in there, waiting to be addressed. The same enormity that hides your bugs is the reason novelty is inexhaustible.
First appearance of the device that every limit in this class gets: what it forbids, and what it opens. A space small enough to audit would be a space too small to be interesting.
The Library of Babel holds every possible book: every truth, every refutation — and overwhelmingly, gibberish. Its inhabitants go mad: containing every truth is worthless without a way of finding one.
Modern echo: a large language model already "contains" astonishing amounts of text. Containment was never the hard part.
410 pages, 40 lines, 80 characters, 25 symbols. The shelves hold 251,312,000 books ≈ 101,834,097 volumes.
From storage to search: from having the answer somewhere to knowing it when you see it.
Write a program that treats all of memory as one integer and increments it. It enumerates every state the machine can be in. It will have turned to dust before getting anywhere — but suppose it ran.
Once in a while, an enormous while, the state would encode Beethoven's Fifth, or the human genome. Without any intelligence whatsoever. And the machine could not select those states over the others.
Evolution is that program with a selector attached: enumerate DNA by mutation, select by reproductive success. A physical process bound by physics, modelled by a computer bound by logic.
Lots of time, or mutate fast. Lots of space, or be tiny. Lots of energy, or be efficient. A few more zeroes in a number make all the difference — in life and in computing.
Everything is bits: numbers, negative numbers, overflow, characters, text, files, images, code. The same 85 in five different notations, and what the machine makes of each.