从哥德尔编码到图灵完备：加法和乘法就够模拟一切计算

PoniesModus · x · 2026-10-18

一场关于哥德尔不完备定理与计算理论的推文讨论：只要理论 T 具有可枚举公理且 T ⊢ φ，就能在 PA（皮亚诺算术）中证明「T ⊢ φ」——即加法和乘法足以编码任意推理，数学天然图灵完备。

提问者惊讶于「如果 P 则 Q」如何只用加法与乘法编码，作者回应展示了用哥德尔 β 函数和中国剩余定理编码有限序列的方法。