Posts

Four grammar classes, four machine classes, one ladder. Why you can't parse HTML with a regex, stated as a theorem.

One machine simulates all others. Interpreters, VMs, and the stored-program computer are all this one theorem.

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.

Averages of independent things are exponentially unlikely to stray.

Why a dynamic array's O(n) resize is still O(1) per push, and how to prove it rather than hand-wave it.

Lower bounds by playing against the algorithm: finding max and second-max needs n + ceil(log n) - 2 comparisons.

Expectations add even when events are hopelessly dependent. Averaging as an existence proof: if the mean is 5, some input hits 5.

A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.

Entropy is the exact floor on lossless compression. Where "information" stops being a metaphor.

Collisions arrive at sqrt(N), not N. Sets every hash length, UUID size, and nonce width you will ever choose.

Agreement over a lossy channel is impossible. Why exactly-once delivery is a lie and idempotency is the real answer.

Systems mirror the communication structure of the organizations that build them. Empirical, not proven — and the inverse maneuver as its practical use.

Every non-trivial semantic property of programs is undecidable.

No program decides termination for all programs. The ancestor of every other undecidability result.

Some infinities are bigger; there are more problems than programs. The proof technique that The Halting problem and Godel's incompleteness theorems both reuse.

Amdahl's rebuttal, and then the law that adds a negative term for coordination: past a point, more nodes make it slower.

The serial fraction caps your speedup, brutally. Pure algebra, not an observed regularity — the empirical part of the speedup story belongs to Gustafson's law and...

Every observable behavior of your API is depended upon by someone; and the robustness principle that made that worse, plus the modern case against it.

Any algorithm that shrinks some inputs must grow others. Kills every "compresses random data" claim on sight.

n+1 items, n boxes, one collision. The cheapest impossibility argument in existence, and the seed for No universal lossless compressor and The birthday bound.