How addition and multiplication alone encode logic: Gödel encoding makes math Turing complete
PoniesModus · x · 2026-10-18
A tweet thread on Gödel's theorems and computation: if a theory T has recursively enumerable axioms and T ⊢ φ, then PA ⊢ (T ⊢ φ) — meaning addition and multiplication alone suffice to encode arbitrary mathematical reasoning, making math naturally Turing complete.
When asked how "if P then Q" can be encoded with just addition and multiplication, the author explains lists can be encoded via Gödel's beta function using the Chinese remainder theorem.
Related event: Addition and Multiplication Alone Suffice to Simulate Turing Machines(4 posts)→