Everything you can write down can be listed. So a program is a number — and a compiler is arithmetic.
No counting needed — just a perfect pairing. Every left has exactly one right, and nothing is left over. That is how you know your two hands have the same number of fingers without counting.
So there are as many even numbers as numbers: pair n with 2n. The part is as big as the whole. Galileo found this disturbing in 1638. Cantor made it the definition.
A set pairable with 1, 2, 3, … is called countable. It can be listed: first, second, third, and every element at some finite position.
A program is a finite string of symbols. So is a proof, a specification, a sentence, a grammar, a score, a formula, a prompt.
List all strings of length 0, then length 1, then 2, then 3 … Every finite text appears at some finite position.
So all C* programs that will ever exist form a countable list. Same for all RISC-U binaries. Same for all proofs. Same for all sentences of English.
This is not saying notation is small. Countable is already infinite. It is saying notation is finite-and-discrete, and finite things line up.
If every text has a position on the list, every text has a number. The simplest version you already know: write the ASCII codes one after the other. A text is a very long integer.
Gödel used this in 1931 to make arithmetic talk about arithmetic. The method carries his name: Gödel numbering.
Once notation is a number, a program can read a program, run a program — and, once a program can read programs, read itself. Every computer you have ever used is this idea in metal: code is data.
The -o option writes the number to a file. The first four bytes, 7f 45 4c 46, spell ELF: the file format every Linux program uses, so this number runs on real RISC-V hardware too.
The -l option reads the number back and the -m option runs it — on an emulated machine, inside selfie. The program that just printed the synopsis is a number that selfie computed from a text that is selfie.
Stage one: a C compiler you did not write produces a selfie. Stage two: that selfie compiles selfie.c into selfie1.m. Stage three: selfie1.m, running on the emulator, compiles selfie.c into selfie2.m.
selfie1.m and selfie2.m are identical: 188,392 bytes, the same number. The compiler agrees with itself. What that does not prove is the subject of week 8.
Nothing on this deck needed anything but the fact that texts are numbers. The compiler is a function from one number, selfie.c, to another, selfie.m. The emulator is a function from a number and an input to what the number does.
Self-reference is not a trick. It is the price of being expressive enough to be useful — and the instrument with which, in two weeks, we find exactly where expressiveness ends.
The same 188,392 bytes are a program to the emulator, data to the compiler that wrote them, and, next week, the tape of a universal machine. Nothing in the bytes says which. You have heard this before.
Programs: countable. What a program does — its answer on every input, an infinite sheet of yes and no — is that countable?
Week 7 proves that it is not, with an argument three lines long that is the most consequential of the twentieth century. Week 6 first builds the machine that runs the programs, so that we know exactly what a behaviour is.
The machine: RISC-U, code and data in one memory, the emulator that runs every program written for it — including itself.