Parity Is Not in AC^0

Symptom You have just read T030 and you are demoralized. Relativization kills the techniques that treat machines as black boxes. Natural proofs kill the combinatorial ones, assuming pseudorandom functions exist. Between them they appear to rule out everything anyone knows how to do, and the honest summary of fifty years is that nobody can prove any interesting problem is hard. ...

The No-Cloning Theorem

Symptom You have spent this whole part learning that information wants to be copied. Entropy bounds compression (T018), Huffman hits the bound (T020), redundancy buys error correction (T021). Every result so far treats “make another copy” as the free operation — the thing you do without thinking, the reason cp has no interesting failure modes. ...

The Nyquist–Shannon Sampling Theorem

Symptom Your dashboard shows CPU utilization averaging 40%, comfortably under budget. Users are reporting timeouts. You add more logging and the average stays at 40%. Eventually someone captures a one-second trace and finds the truth: the service spikes to 100% for eight seconds out of every ninety, and your monitoring samples every sixty seconds. The spikes are real, periodic, and invisible. ...

The Hamming Bound and Error-Correcting Codes

Symptom You are specifying ECC memory for a fleet. The vendor quotes SECDED: single error correct, double error detect, at 8 check bits per 64 data bits. That is 12.5% overhead, and someone in the room asks the obvious question — why not correct two errors? Or three? What does it cost? ...

The Universal Machine

Symptom You write a Python program. It runs. What ran it? CPython — itself a program, written in C, compiled to x86 instructions, executed by a CPU whose control unit is arguably interpreting microcode, possibly inside a virtual machine, on a kernel that scheduled it, all perhaps within a container image. At no point in that stack does anyone find it strange that a program’s job is running other programs. We build emulators, JITs, WebAssembly runtimes, Docker, QEMU, and browsers that download and execute arbitrary code from strangers, and treat every layer as ordinary engineering. ...