Gödel's flip side: addition and multiplication alone make math Turing complete
jessi_cata · x · 2026-10-17
The author highlights an often-overlooked flip side of Gödel's incompleteness results: beyond limiting Hilbert's program of formalizing math, they show how easily mathematics becomes Turing complete.
The argument: if a theory T has recursively enumerable axioms and T ⊢ φ, then Peano Arithmetic (PA) can prove the provability statement "T ⊢ φ". In other words, addition and multiplication alone suffice for a formal system to encode arbitrary computation—the theoretical basis for provability logic and program verification tools.
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