Scott Aaronson shows Rosser's theorem via Turing machines, no arithmetic encoding needed
jessi_cata · x · 2026-10-17
Scott Aaronson's blog post walks through a proof of Gödel's First Incompleteness Theorem (in Rosser's stronger form) using computability theory instead of the traditional arithmetic encoding.
Key points:
- Gödel's original proof, and the CS-favorite alternatives, only directly yield the weaker "no sufficiently powerful system is both complete and consistent" statement — a persistent pedagogical annoyance in Aaronson's undergrad computability course.
- The writeup also highlights the flip side: incompleteness shows how easily math becomes Turing complete. If a theory T has r.e. axioms and T ⊢ φ, then PA ⊢ (T ⊢ φ) — addition and multiplication suffice.
More from Research
- CoPE adds one forecasting loss to GRPO, doubling long-horizon agent sample efficiency — Lianhuiq · 2026-10-17
- Debate: neural networks are built to be read — is mech interp easier than claimed? — basedjensen · 2026-10-17
- Design Arena analysis: beige serif websites went from loved in Q1 to hated in Q4 — soleio · 2026-10-17
- Mech interp researcher warns the field could be net negative for the world — ArthurConmy · 2026-10-17
- Local LLMs get a benchmark for what they can actually do on your machine — draginol · 2026-10-17
- MSR: Test-Time Method Externalizes Diversity to Corpus-Derived Sampling for Generative Models — Kostas Triaridis · 2026-10-17