2.1 计算模型与丘奇-图灵论题

2.1 计算模型与丘奇-图灵论题

本节摘要：图灵机是计算的标准模型，但为什么是它？本节讲清楚图灵机的定义、几种变体（多带、非确定性）为什么都等价、丘奇-图灵论题说了什么、以及它为什么是论题不是定理。读完你能理解"可计算"的严格定义为什么落在图灵机上。

一、图灵机定义

图灵机 1936 年由图灵提出，是个抽象计算模型。形式化定义：

M = (Q, Σ, Γ, δ, q0, q_accept, q_reject)

• Q：有限状态集
• Σ：输入字母表（不含空白符）
• Γ：带子字母表（含空白符）
• δ：转移函数 Q×Γ → Q×Γ×{L,R}
• q0：起始状态
• q_accept/q_reject：接受/拒绝状态

直观理解：一条无限带子，上面有格子，每个格子写一个符号。一个读写头在带子上，读当前格子符号，按转移函数决定：写什么新符号、移到哪个状态、读写头左移还是右移。进入接受状态则接受输入，拒绝状态则拒绝，否则一直运行。

这个简单模型惊人地强大——它能模拟任何现代计算机能做的计算。图灵的洞察是：把"人在纸上算"的过程抽象成机器动作，得到了计算的本质模型。

二、图灵机的几种变体

基本图灵机有多种扩展，但都和基本图灵机等价（互相模拟）：

多带图灵机：多条带子多个读写头。看起来更强，但能被单带图灵机模拟（单带编码多带内容），所以等价。

非确定性图灵机（NTM）：转移函数可能多值，"猜测"走哪条。看起来更强，但能被确定性图灵机模拟（广度优先遍历所有分支），所以等价。注意：可计算性等价（都能算），但复杂性可能不同（NTM 可能快很多，这是 P vs NP 的根源）。

双向带子图灵机：带子两端无限。和单向带子等价。

这些等价性说明：图灵机的"计算能力"不依赖具体细节，是模型的本质属性。怎么加扩展都不改变能算什么，只改变算多快。

图 2-1 图灵机模型

三、丘奇-图灵论题

论题陈述：任何能被"直观计算"的函数，都能被图灵机计算。

这不是定理——"直观计算"无法严格定义，所以无法证明。但所有提出的"合理"计算模型都和图灵机等价：

• λ 演算（丘奇）：函数式，和图灵机等价。
• 递归函数（哥德尔）：数学式，和图灵机等价。
• 寄存器机、马尔可夫算法、甚至现代编程语言：都等价。

这种"普适性"强烈支持论题。所以"图灵机可计算"被当作"可计算"的定义。

论题的意义：它划定了计算的边界。如果某问题图灵机算不了，那任何合理模型都算不了——问题本质不可计算，不是模型不够强。这让"不可判定"成为绝对概念，不依赖具体模型。

四、论题为什么是论题不是定理

因为"直观计算"无法形式化定义。要证明论题，得先严格定义"直观计算"，但任何定义都引入新假设，可能被质疑。

图灵的原始论证：分析"人在纸上算"的过程——人眼读符号、人脑决定动作、手写新符号、移到新位置。把这些抽象成机器动作，得到图灵机。这个论证有说服力但不是形式证明。

所以论题是"经验性论题"——所有证据支持它，但没法数学证明。如果未来发现更强的计算模型（如能算图灵机算不了的），论题会被推翻。但目前所有尝试（包括量子计算）都没突破图灵机边界——量子机能算的，图灵机也能算（只是慢），所以论题至今成立。

五、通用图灵机

图灵机最惊人的特性：存在"通用图灵机"U，能模拟任何图灵机。

机制：把任何图灵机 M 的描述编码成串 ⟨M⟩，U 以 ⟨M⟩ 和输入 x 为输入，模拟 M 在 x 上的运行。U 是"可编程的"——换 ⟨M⟩ 就模拟不同的机器。

这预示了现代计算机——CPU 就是个通用图灵机，程序是 ⟨M⟩，输入是 x。图灵 1936 年就预见到了"存储程序计算机"的概念，比第一台真实计算机早十年。

通用图灵机的存在，让"计算"有了统一框架——所有计算都是通用图灵机跑不同程序。这也是后面不可判定性证明的基础——既然程序能作为输入，就能构造"对程序本身做判断"的悖论。

六、图灵机与现代计算机

图灵机能模拟现代计算机吗？能，但有几点注意：

• 无限带子 vs 有限内存：图灵机带子无限，计算机内存有限。严格说计算机是有限状态机，能算的图灵机都能算（图灵机能模拟有限状态机）。但计算机内存足够大时，行为接近图灵机，所以实践中用图灵机模型。
• 整数运算 vs 实数：图灵机处理离散符号，不能直接处理实数。实数计算用图灵机的近似（有限精度）或用"实数计算模型"（Blum-Shub-Smale），但主流计算理论用图灵机。
• 并发/网络：图灵机是顺序模型，但并发能用多个图灵机模拟，网络能用图灵机模拟通信，所以不突破图灵机边界。

结论：图灵机是计算的合理抽象，现代计算机能算的图灵机都能算，图灵机算不了的现代计算机也算不了。

七、超越图灵机？

有没有比图灵机更强的计算模型？这是"超计算"（hypercomputation）研究的问题。

提议的超计算模型：

• 谕示机：图灵机加一个"谕示"（能瞬间回答某问题的黑盒）。能算图灵机算不了的，但谕示不存在，是理论工具。
• 实数计算：处理实数的模型，能算图灵机算不了的实数问题，但需要无限精度，物理不可实现。
• 量子计算：能加速某些问题（Shor 算法），但不能算图灵机算不了的，只是更快。
• 相对论/量子引力计算：利用物理奇点（如黑洞、时间循环）做超计算，纯理论，物理不可实现。

目前没有物理可实现的超计算模型。丘奇-图灵论题至今成立——图灵机界定了物理可实现的计算边界。

⚠️ 常见误读：以为"量子计算机能算图灵机算不了的"。错。量子计算机能加速某些问题（指数加速），但不能算图灵机算不了的——它只是更快，计算能力（能算什么）和图灵机相同。

💡 关键直觉：图灵机是计算标准模型，所有变体（多带/非确定性）等价。丘奇-图灵论题（非定理）说所有合理模型等价，所以图灵机可计算=可计算。通用图灵机能模拟任何机器，预示现代计算机。量子计算更快但不突破图灵机边界。

重点提炼

• 图灵机：无限带子+读写头+有限状态控制，转移函数决定动作，1936 年图灵提出。
• 变体等价：多带、非确定性、双向带子都和基本图灵机等价（互相模拟），计算能力不变，只改变速度。
• 丘奇-图灵论题：任何直观可算的都能被图灵机算，是论题非定理（"直观计算"无法严格定义），所有合理模型等价强烈支持。
• 论题意义：划定计算边界，图灵机算不了的任何合理模型都算不了，"不可判定"成绝对概念。
• 通用图灵机：能模拟任何图灵机（以机器描述为输入），预示存储程序计算机，是现代 CPU 的理论原型。
• vs 现代计算机：图灵机能模拟计算机（有限内存近似无限带子），计算机能算的图灵机都能算。
• 超计算：谕示机/实数计算/量子引力等提议，但无物理可实现模型，丘奇-图灵论题至今成立。
• 量子计算：加速某些问题但不突破图灵机边界，能算的图灵机也能算（只是慢）。