A first-semester class, in fourteen weeks, that answers its title with a definition — and earns it.
↑ Introduction to Computer Science
proof · notation · syntax · truth · meaning · semantics
Not how to use a device. Not how to prompt a chat bot. Not even, mainly, how to code.
The principles were true before this technology arrived and will be true after whatever replaces it. That is why nothing in this class mentions a product, a vendor, or a year.
By the end you can say, about any machine that talks, exactly what it is and what it cannot be — and check the answer yourself.
Is it intelligent? — badly posed, as the talk said. We replace it with questions you can answer: what language, what semantics, what metric, what budget, who checks.
Intelligence is developing new formal languages — or new properties in existing ones — which requires discovering and understanding promising unproven truth. Fourteen weeks to earn it.
Finite. Bits, and how fast a few of them outnumber the atoms in the universe. Week 2 and 3.
Countable. Everything you can write down: programs, proofs, machines — and the machine that reads them. Weeks 4 to 6.
Uncountable. What you mean by it. Behaviours, truths. Cantor, Gödel, Turing, Rice — then the compiler and the operating system built anyway. Weeks 7 to 10. Then cost, machines, and the answer.
| wk | lecture | in the terminal | |
|---|---|---|---|
| 1 | — | The talk, then the class | ./selfie |
| 2 | I | Size: bits, state spaces | -c selfie.c |
| 3 | I | Everything is bits | examples/ |
| 4 | II | Notation: EBNF, C*, RISC-U | -s |
| 5 | II | Countability; the fixed point | make self-self-check |
| 6 | II | The machine: RISC-U, mipster | make emu, -d |
| 7 | III | Uncountability: the diagonal | — |
| wk | lecture | in the terminal | |
|---|---|---|---|
| 8 | III | Self-reference I: Gödel | make self |
| 9 | III | Self-reference II: halting, Rice | -d on a loop |
| 10 | III | Systems: emulation ≡ virtualization | make os-emu |
| 11 | IV | Cost: P vs NP, SAT, Landauer | make sat |
| 12 | IV | Formal methods: rotor, bitme | make rotor |
| 13 | V | Machines: LLMs, the gate | a prompt |
| 14 | VI | What is intelligence? | — |
A compiler for a tiny subset of C, an emulator for a tiny subset of RISC-V, and a hypervisor — twelve thousand lines, one file, written in the language it compiles.
Three commands: the compiler compiles itself, the emulator executes itself, the hypervisor hosts itself. Understand the first and you understand compilers; the second, machines; the third, operating systems.
And a workshop of tools around it that turn a program into a logical formula and hand it to a solver — where this class meets the frontier, in week 12.
What is Intelligence? — this class is its first six parts at talk resolution, one chapter per week or so. It is in the repository under book/.
This class has no formal assignments. It has a recommended exercise list per week — reading, the commands of the session to rerun, a few paper exercises — and one thing to try on the autograder, which is how the compiler and systems classes are graded.
Formal languages are not casual. Everything matters, even the tiniest detail, and the trick to learning them is to take steps so small they are almost painful.
Every negative result in this class — there are five — is read twice: what it forbids, and what it opens. The second reading is the one to remember.
Whatever intelligence is, humour is the only way.the last slide of the talk, and of week 14
Beethoven · Symphony No. 3 “Eroica” — Bernstein, Vienna Philharmonic. A symphony that invented a new language for the form — twice the length of anything before it, and every later symphony is written in the language it made. The definition, in E flat.
Gödel, Escher, Bach — Hofstadter, 1979: Gödel, Bach and Escher as three renderings of one loop, the book this class’s spine grew out of. And, more technical, On the cruelty of really teaching computing science — Dijkstra, 1988: why the small steps are not optional.