The Lambda Calculus and the Y Combinator
Three rules, all of computation, and recursion built from nothing. Absorbs Church–Rosser confluence: reduction order doesn't change the answer.
Computability
Kolmogorov Complexity
The length of the shortest program producing a string. Uncomputable, and the correct definition of "random" and "simple".
Reductions
"Solve A by solving B" is how undecidability and hardness both spread. The mechanical skill behind Parts II and IV.
Kleene's Recursion Theorem
Any program can obtain its own source. Quines aren't a party trick; self-reference is guaranteed by the model.
The Universal Machine
One machine simulates all others. Interpreters, VMs, and the stored-program computer are all this one theorem.
The Church–Turing Thesis
Every reasonable model of computation computes the same functions. Why "it's Turing-complete" is a meaningful thing to say about CSS, SQL, and your YAML config.
Rice's Theorem
Every non-trivial semantic property of programs is undecidable.
The Halting Problem
No program decides termination for all programs. The ancestor of every other undecidability result.
Cantor's Diagonal Argument
Some infinities are bigger; there are more problems than programs. The proof technique that The Halting problem and Godel's incompleteness theorems both reuse.