Everything that follows is built from one distinction: the difference between a proof and the truth.
Those two colours keep those two jobs for the whole half hour: proof, notation, syntax — truth, meaning, semantics.
This entire talk was generated by an AI.
It took me 40+ years to become someone who could prompt it into existence. I could do that today. I could not have done it yesterday. No prior computer science is required to follow what it produced.
What it studies is older than both: notation — what can be written down, and what the marks can and cannot do once they are written.
It met that question where a machine forces the notation to be exact. That is why the limits were noticed here first, and measured here most sharply — and why they hold everywhere else.
So the answer to the title is a definition, stated at the end and earned first. Nothing in the derivation depends on which computer, which language, or which year.
Computer science is no more about computers than astronomy is about telescopes. attributed to Edsger W. Dijkstra
The short answer, to be earned: computer science is the exact study of the gap between notation and meaning.
| I | Size | why 34 bytes beat the universe |
| II | Infinity | why meanings outnumber notations |
| III | Self-reference | why proof ≠ truth · and where the computer came from |
| IV | Cost | hard to find, easy to check |
| V | Machines | a language model, seen from inside the theorems |
| VI | Definition | what computer science is · and a specimen to run |
Four of these parts end in a theorem that sounds like bad news. Each one turns out to mark the place where the subject begins.
First a feeling for how big the spaces are that programs live in — because everything later, including every bug and every AI, happens inside one.
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.
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.
Selfie is the specimen this talk uses: one file of C, containing a compiler, an emulator and a hypervisor, each of which is applied to itself. Small enough to read to the end — which turns out to be the only way a meaning is ever actually pinned down.
The machine it runs on has 4 GB of memory — 235 bits. Written out in decimal, its state count has about 10.3 billion digits: 3.4 million pages, some 6,900 volumes of 500 pages. That shelf does not hold the states. It holds the number of them, written down once.
Every program selfie will ever run, and every bug in any of them, is one point in that space.
Test a billion states per second, starting at the Big Bang, and by now you would have checked about 288 of them — out of 234,359,738,368.
The fraction is not small. It is indistinguishable from zero.
Testing shows the presence, not the absence of bugs.Edsger W. Dijkstra, 1969
So knowing what a program does cannot be exhaustive search. It has to be argument, structure, abstraction — which is to say, notation. That is where Part III begins.
Vast is still finite. Now the things that are not — and the discovery that endlessness comes in two sizes.
Two sets are the same size if you can pair them up, one to one, nothing left over. A set pairable with 1, 2, 3, … is countable: it can be listed.
A program is a finite string of symbols. So is a proof, a specification, a prompt. List all strings of length 1, then 2, then 3 … every finite text appears at some finite position.
So all programs that will ever exist form one list. Same for all proofs. Same for all prompts anyone will ever type.
Giving each piece of text a number is Gödelisierung — Gödel numbering. selfie.c is 365,784 characters: one string, one very long number. It is how a machine reads a machine, and Part III is built on it.
A behaviour is an endless answer sheet: for input 1, yes or no; for input 2, yes or no; forever. Every infinite bit string is one. Suppose they could be listed: S1, S2, S3, …, every behaviour somewhere on the list.
Go down the diagonal and ask each row about its own number. What does S1 say about 1? S2 about 2? Sn about n?
Build D by answering the opposite every time: D(n) = not Sn(n). Nothing exotic — a rule anyone can apply, one number at a time.
D is not S1: they disagree about 1. Not S2: they disagree about 2. Not Sn, for any n. So the list left something out — and it was any list at all. Cantor, 1891.
Programs: countable. Behaviours: uncountable. So almost every behaviour has no program.
Proofs: countable. Truths about numbers: uncountable. So almost every truth has no proof.
Prompts: countable. Things you might mean by one: uncountable. So almost everything is unsaid.
No vocabulary — mathematical, legal, neural — will ever cover the space of meanings. Every new notation captures meaning that was unreachable before, and there is always more left. The supply never runs out.
Counting says the gap exists. Self-reference walks to the edge and points — and the same step, taken forwards, builds the computer.
What does while mean? Not what the manual says. What it means is whatever the compiler emits — a comparison and a branch — and whatever the machine then does with those.
So the meaning of a program is fixed by another program. And selfie's compiler, starc, is written in the very language it gives meaning to.
An English dictionary written in English. Only paradoxical if you demand that the definitions come first. They do not: the machine comes first, and the dictionary is bootstrapped onto it.
Syntax is the text — finite, checkable, copyable. Semantics is what the machine does with it — over all inputs, forever. A semantics is a function from the first to the second, and pinning that function down is the founding act of every exact discipline.
The first is Gödel's move: a text handed to itself. The second is Turing's: a machine handed its own description. The third is what an operating system is. All three run on a laptop.
By Gödelisierung, build a sentence that says "this sentence has no proof in this system." If it were provable, the system proves a falsehood. So it is unprovable — and therefore true. Adding it as an axiom does not help: the construction runs again.
Selfie's fixed point proves the compiler agrees with itself. It cannot prove the binary does what the source says: a compiler can carry a back door that reinserts itself on every self-compilation, invisible in clean source. The check has to come from outside — a second, independent compiler.
Proof is a finite object you can check. Truth is not. Proof is syntax. Truth is semantics. They are not the same size — and nothing certifies itself.
Suppose H(P,x) decides, for every program and input, whether P halts on x.
Build D(P): ask H whether P halts on P — then do the opposite.
Now run D(D). It halts exactly if it doesn't. Contradiction. So H never existed.
Turing, 1936 — the same paper that defined the universal machine, and thus invented the computer. The limit and the machine arrived together.
A machine used to be its job. Turing's move: put the machine's description on the tape, as data. Then one machine U reads any description and does whatever that machine would do. That is universality: one piece of hardware, every possible behaviour, because the behaviour arrives as notation.
Your phone is not phone-shaped. It is U holding a description — which is why a new app needs no new hardware.
mipster reads a word of RISC-U code, does what it says, and advances. Fourteen instructions, and it runs every program that will ever exist for that machine — including itself. That is the second of the three commands.
Hand a decider its own description: contradiction, no H. Hand a machine any description: every program at once, one U. Turing published both in 1936.
Does it parse? How long is it? Which procedures does it call? Are the types consistent? Does it contain a loop? A compiler answers all of these, always, in finite time.
Does it terminate? Is it equivalent to that one? Can it divide by zero? Does it leak the key? Is it correct? No program decides any of these for all programs — whoever, or whatever, wrote them.
So every useful tool — a type checker, a test suite, a fuzzer, a model checker, a proof assistant — is a deliberate approximation: sound but incomplete, or complete but unsound, or exact only within a bound. Choosing which to give up is the discipline. Selfie ships several such choices, applied to selfie.
| year | who | the list | the diagonal object |
|---|---|---|---|
| 1891 | Cantor | all behaviours | a row on no list |
| 1901 | Russell | all sets | the set of non-self-members |
| 1931 | Gödel | all provable sentences | "I am unprovable" |
| 1936 | Tarski | all definable predicates | "I am false" |
| 1936 | Turing | all decidable questions | a program that defies its judge |
| 1953 | Rice | all semantic properties | all of the above, at once |
Assume a complete list. Ask each item about itself. Answer the opposite.
Learn the move once and you own the century.
Suppose a question is decidable. You still have to pay for the answer — in time, space, and energy.
Given a logical formula over 100 yes/no variables: is there an assignment making it true? Perfectly decidable — try all 2100.
monster and rotor translate RISC-U machine code — including all of selfie — into exactly such formulae, satisfiable when some input makes the code fail. Syntax becomes semantics, and then hits this wall, before the coffee gets cold.
That asymmetry has a name: NP — problems whose solutions are quick to verify even if finding them seems to need exponential search.
Cook and Levin, 1971–73: thousands of such problems are the same problem in disguise. Crack one efficiently and you crack scheduling, routing, folding, packing, proving.
Whether that is possible — P = NP? — is the most consequential open question in the exact sciences. Most researchers bet no.
Writing a proof versus reading it. Designing a protein versus assaying it. Writing the program versus running the test. Doing the homework versus grading it.
Generation is expensive; verification is cheap. Every division of labour that works — between people, or between a person and a machine — sits on that gap. Part V comes back to it.
Landauer, 1961: erasing one bit at room temperature costs at least kT ln 2 ≈ 3 × 10-21 joules — because erasing is irreversible: two states become one, and the lost distinction leaves as heat. Information is physical.
A search moves on, and moving on is erasing. Just counting through our 266-bit space flips the lowest bit 2266 times, each flip an overwrite: ≈ 1059 J, about 1015 times everything the Sun will ever radiate. You cannot even count the states.
Meanwhile a human brain runs on 20 watts: a dim light bulb, doing what data centres cannot.
The bill is for any machine that forgets as it goes — every machine ever built; reversible computing lowers it in principle, at the price of time and of error correction, which forgets again. Time, space, energy: one budget. Any claim about intelligence that ignores it is a claim about magic.
Now the machine everyone is asking about. It is a computation — so it is subject to every single thing we have just established.
The name is exact. What a large language model — an LLM — is trained on is language, so the signal is syntactic: which symbol follows which. Meaning is never handed to it.
That this works as well as it does is the genuine surprise of the decade. It cost megawatts for weeks; you run on twenty watts. Neither figure changes what kind of object it is.
Billions of parameters, each many bits. Part I applies unchanged: that space cannot be inspected, so the behaviour cannot be enumerated. Only sampled.
Fluency is syntax. Correctness is semantics. We built a machine of extraordinary fluency, so the gap between the two is something you now meet before breakfast.
Not a defect to be patched away: it is the proof/truth distinction at consumer scale. Generated code compiles, reads well, and is wrong in the same way a proof-shaped paragraph is wrong.
So the only thing that settles it is a check against something with a semantics — a compiler, a test, a proof, a measurement, an experiment.
Not from the model: it was trained on symbols defined by other symbols. From outside it. Part III already said the check is always external — Gödel's stronger system, Thompson's second compiler. Here it is, at consumer scale.
Everything so far was true before the machine arrived and stays true after it. Now the answer to the title — and a specimen to run.
Prompt in English, and what comes back is plausible notation: fluent, confident, and Part V says nothing about whether it is true.
Two things can happen next. Unchecked, the answer is simply accepted — and then there is no semantics anywhere in the loop.
Checked, it meets a compiler, a test, a proof, a measurement — a semantics in Part III's exact sense — and is kept or sent back round. That gate is the one part of the loop the machine does not supply.
The machine is where notation is forced to be exact, so the gap was noticed here first and measured here most sharply. But the theorems hold for any notation: a statute, a genome, a score, a model.
No final language (Cantor), no complete system (Gödel), no self-certificate, no decision procedure for meaning (Rice). The subject cannot be completed — a property of the subject, not a complaint about it.
Test it: a compiler, an operating system, a proof assistant, a language model — each is notation given a meaning by a machine, and each is bounded by Parts I to IV. None of them is outside the definition.
C*: 7 keywords, one type and pointers to it. starc gives it a semantics — and starc is written in C*, so the dictionary is written in the language it defines.
RISC-U: 14 instructions, 32 registers, 4 GB. mipster interprets it — one universal machine, a page of C per instruction group, running every program for that machine, itself included.
Selfie compiles itself and gets the same bytes twice — proof that it agrees with itself, and Thompson says what that cannot prove. So the tools around it turn its execution into logic, and are applied to selfie and to themselves: the outside checks, built in.
A final language. A complete system. A machine that certifies itself. A decision procedure for meaning. A search that reaches every state, or an energy budget that could pay for one.
Every notation not yet invented, every truth not yet proved, every behaviour not yet written down — an unbounded frontier in a subject that, by its own theorems, cannot be finished.
The halting problem, applied to the subject itself:
this computation does not terminate.
Computer science is the field that measured it — not to close it, which four theorems say cannot be done, but to say exactly where it is.
That is the whole answer. One slide left: the sources, and the specimen, ready to run.
Cantor 1891 · Russell 1901 · Gödel 1931 · Tarski 1936 · Turing 1936 · Rice 1953 · Cook 1971 · Karp 1972 · Levin 1973
Landauer 1961 · Dijkstra 1969 · Thompson, Reflections on Trusting Trust 1984 · Wheeler 2005
Or docker run -it cksystemsteaching/selfie. It also runs in a browser tab.
/intelligence — the same argument, an hour long, for any field.
/talk — the three commands, explained.
Kirsch, Elementary Computer Science: From Bits and Bytes to the Universality of Computing — built on the specimen.
github.com/cksystemsteaching/selfie