A deep dive into the fundamental limits of computation, logic, and systems — Gödel, Turing, Arrow, CAP, and beyond. Proven impossibilities and open conjectures that every engineer and thinker should know.
cloudstreet-dev.github.io/impossibility-theorems
Nine chapters covering the most important impossibility results across mathematics, computer science, economics, distributed systems, and cybernetics:
- Gödel's Incompleteness Theorems — Why no consistent formal system can prove all truths about arithmetic, and why mathematics cannot verify its own foundations.
- The Halting Problem — Turing's proof that no algorithm can determine whether an arbitrary programme terminates, and what that means for programme analysis.
- Rice's Theorem — The sweeping generalisation: no non-trivial semantic property of programmes is decidable.
- Arrow's Impossibility Theorem — Why no ranked voting system with three or more candidates can satisfy a minimal set of fairness axioms.
- The CAP Theorem — The inescapable trade-off between consistency, availability, and partition tolerance in distributed systems.
- Zooko's Triangle — Why naming systems cannot be simultaneously human-meaningful, secure, and decentralised.
- The RUM Conjecture — The three-way trade-off between read overhead, update overhead, and memory overhead in storage engine design.
- Ashby's Law of Requisite Variety — Why a controller must be at least as complex as the system it regulates.
- Open Conjectures and What These Limits Mean — P vs NP, the extended Church–Turing thesis, and what impossibility results mean for practising engineers.
Install mdBook, then:
mdbook serve --openThanks to Georgiy Treyvus, CloudStreet Product Manager, for the idea for this book.