仅靠加法与乘法即可在算术中模拟图灵机

多篇帖子围绕同一主题展开：在皮亚诺算术（PA）中仅用加法与乘法即可模拟图灵机，从而证明数学天然图灵完备。方法是把纸带按状态数进制编码成两个自然数（分别对应磁头左右两侧），并借助基于中国剩余定理的哥德尔 β 函数实现列表编码。讨论还指出哥德尔不完备定理常被忽略的另一面：只要理论 T 具有可递归枚举的公理且 T ⊢ φ，就能在 PA 中证明「T ⊢ φ」，说明加减乘除足以编码任意推理，也揭示了希尔伯特形式化纲领的局限。

2026-10-17 ~ 2026-10-18 · 4 条相关

• 哥德尔定理的另一面：加法乘法足以让数学图灵完备 — jessi_cata · 2026-10-17
• 从哥德尔编码到图灵完备：加法和乘法就够模拟一切计算 — PoniesModus · 2026-10-18
• 用纯加减乘除模拟图灵机:把纸带编码成一个自然数 — jessi_cata · 2026-10-18
• 用哥德尔 β 函数在皮亚诺算术里编码图灵机纸带 — jessi_cata · 2026-10-18