用纯加减乘除模拟图灵机:把纸带编码成一个自然数

jessi_cata · x · 2026-10-18

jessicata 解释如何只用皮亚诺算术(加法与乘法)模拟图灵机:把「纸带可能状态数」当作进制(如 10 进制),用两个数分别编码磁头左侧和右侧的纸带内容。例如左数 43580、右数 39921 表示纸带为 00043580[]12993000,其中 [] 是磁头。

这样「读左/右符号」「滑动纸带」都变成简单的除法、取模和乘法运算:读右侧紧邻符号即右数 mod 10;写入符号 5 并右移时,新左数 = 左数×10+5,新右数 = 右数÷10。以此回应「if P then Q 如何只用加法乘法编码」的提问。