可计算性理论

在第一台电子计算机被制造出来之前整整十年，数学家们已经严格地证明了：某些问题，无论计算机有多强大，永远无法被程序所解决。这不是工程的局限，而是数学的边界——一条永远不会因为技术进步而后退的线。

可计算性理论研究的正是这条边界：什么样的问题在原则上是可以被机械化地求解的，什么样的问题在原则上不行，以及这两者之间的区分意味着什么。

破除误解：不可判定性不是"现在做不到"#

"停机问题不可判定"常被误解为"我们目前还没找到解法"。这是根本性的误解。

不可判定性是一个数学定理：可以用严格的逻辑证明，不存在任何能正确解决该问题的程序——不是"还没找到"，而是"不可能存在"。这个结论不依赖当前计算机的速度、内存或架构，对任何物理上可实现的计算装置都成立（在邱奇-图灵论题的框架内）。

现场：1930 年代的数学危机#

可计算性理论诞生于 20 世纪 30 年代数学界的一场根本性危机。

大卫·希尔伯特在 1900 年前后雄心勃勃地提出：数学应该被建立在一套完备的公理体系上，所有数学真理都应该可以从这套公理推导出来，并且应该存在一种机械程序，能判断任意数学命题的真假（这就是"判定问题"，Entscheidungsproblem）。

1931 年，哥德尔的不完备定理打碎了完备性的梦想：任何足够强的一致公理系统，必然存在不能被证明也不能被否证的命题。随后，图灵和邱奇从不同路径证明了判定问题也无解——不存在能对所有数学命题判定真假的机械步骤。

核心一：图灵机模型#

1936 年，艾伦·图灵在论文《论可计算数及其在判定问题上的应用》中定义了图灵机：

• 一条无限长纸带，分割成格子，每格可写一个符号（来自有限字母表）。
• 一个读写头，可以读取当前格子的符号、改写它、并向左或向右移动一格。
• 一个有限状态控制器，根据当前状态和读到的符号，按规则表决定下一步操作和转换到哪个状态。

图灵机的能力看似极其有限，却被证明与任何已知的计算模型等价。这是可计算性理论的核心直觉："计算"的本质，不在于计算装置有多精巧，而在于能否系统地执行有穷步骤。

核心二：停机问题（Halting Problem）#

停机问题（Halting Problem）：是否存在一个程序 $H$，使得对于任意程序 $P$ 和输入 $x$，$H(P, x)$ 能正确判断 $P$ 在输入 $x$ 上是否会终止？

图灵 1936 年证明这样的 $H$ 不存在。证明采用对角化论证（diagonalization），结构上与康托尔证明实数不可数的方法异曲同工：

假设 $H$ 存在，构造程序 $D$：对输入程序 $P$，$D$ 模拟 $H(P, P)$——如果 $H$ 说 $P$ 会停机，则 $D$ 进入死循环；如果 $H$ 说 $P$ 不停机，则 $D$ 停机。

现在考虑 $D(D)$：如果 $D$ 在输入 $D$ 上停机，则按定义 $D$ 应死循环——矛盾；如果 $D$ 死循环，则按定义 $D$ 应停机——矛盾。因此 $H$ 不可能存在。

停机问题是第一个被证明不可判定的问题，也是最直觉上可理解的一个：你无法写出一个"通用调试器"，对所有程序判断它会不会停。

而且不可判定性远不止停机这一个孤例。莱斯定理（Rice's theorem，1953）把它推广到了惊人的普遍程度：对于程序所计算的函数的任何非平凡语义性质（即并非对所有程序都成立、也非对所有程序都不成立的性质），判定"某个程序是否具有该性质"都是不可判定的。"这个程序会输出 42 吗""这两个程序是否计算同一个函数""这个程序是否永远不崩溃"——只要问的是程序的行为（而非语法形式），答案一律不可判定。这正是为什么完美的自动化软件验证、查毒、等价性检查在原则上不可能存在：莱斯定理保证了它们都归约到一个不可判定的内核。

核心三：邱奇-图灵论题#

与图灵同期，美国数学家阿隆佐·邱奇（Alonzo Church）用 $\lambda$ 演算（lambda calculus）定义了"可计算函数"，并证明了等价的不可判定性结果。随后，克莱尼用递归函数给出了第三种等价定义。

邱奇-图灵论题（Church-Turing Thesis）：凡是"直觉上可以被机械步骤计算"的函数，都可以被图灵机计算。

这是一个论题（thesis），而非定理——它无法在数学内部被证明（因为"直觉上可计算"是非形式概念），但几十年来没有任何已知的计算模型超越了图灵机的计算能力，这给了它极强的经验支持。

物理计算机（量子计算机包括在内，在目前的理论框架中）被认为满足这个论题——量子计算机能更快地解决某些问题，但不能解决图灵机原则上无法解决的问题。

核心四：不可判定问题的层次#

停机问题只是冰山一角。可计算性理论建立了一套对问题难度的精细分类：

此外，Post 对应问题（两组字符串能否通过重排匹配）、希尔伯特第十问题（整系数多项式方程是否有整数解，由 Matiyasevich 等人 1970 年证明不可判定）等，都是著名的不可判定问题。

代价与争议#

哥德尔的幽灵：有哲学家认为，不完备定理和停机问题证明了人类心灵无法被机器模拟——人类能"看到"某个命题的真，即使它无法被形式证明，这一能力超越了图灵机。约翰·卢卡斯（1961）和罗杰·彭罗斯（1994）持这类观点。但多数逻辑学家和哲学家认为，这个论证存在根本性的循环漏洞，并不成立。

物理可计算性：超图灵计算（hypercomputation）的讨论认为，某些理想物理过程（如无限精度模拟量计算）可能超越图灵机能力。这在物理实现上极为存疑，主流计算理论界态度保留。

图灵机的变体：等价性与鲁棒性#

图灵机模型的一个惊人特性是它的鲁棒性：对图灵机进行各种"增强"，并不增加其计算能力：

• 多带图灵机（多条纸带）：可以模拟，且时间上只有多项式放慢（平方级别），不影响可计算能力
• 非确定性图灵机（每步可以"分叉"到多个计算路径）：在可计算性上与确定性图灵机等价（可以用深度优先搜索模拟），但在复杂度上有本质区别（NP 对应非确定性多项式时间图灵机）
• 随机存取机（RAM）：可以常数时间访问任意内存地址，模拟时间开销为多项式级别
• 二维纸带（二维格子而非一维纸带）：仍等价于标准图灵机

这种等价性正是邱奇-图灵论题的经验支撑：无论如何增强抽象计算模型，都无法超越图灵机的计算能力（在可计算性意义上）。唯一的例外是具有"超计算"能力的非物理假想设备（如能求解停机问题的神谕机），而这类设备在物理上无法实现。

递归函数理论：第三条通向可计算性的路#

与图灵机和 λ 演算同期，斯蒂芬·克莱尼（Stephen Kleene）基于库尔特·哥德尔的工作，系统发展了递归函数理论（Recursive Function Theory）：用递归操作定义"可计算函数"类。

起点是几个简单的基础函数（零函数、后继函数、射影函数），通过三种操作——组合（composition）、原始递归（primitive recursion）、μ 算子（minimization operator，即搜索使函数值为零的最小参数）——构造出所有可计算函数。

原始递归函数（primitive recursive functions）是通过组合和原始递归构造的所有函数——这包括加法、乘法、指数、阶乘……几乎所有常见数学函数。有趣的是，存在可计算但不是原始递归的函数：阿克曼函数（Ackermann function，1928）是最著名的例子，它增长极快（$A(3,3) = 61$，$A(4,4)$ 是一个天文数字），无法用有限次原始递归表达，但加上 μ 算子后可以计算。

递归函数、图灵机、λ 演算三者的等价性，由克莱尼在 1936–1943 年间分阶段证明完成，这是邱奇-图灵论题最重要的数学基础。

算法信息论：从计算到随机性#

1960 年代，雷·所罗门诺夫（Ray Solomonoff）、安德烈·柯莫哥洛夫（Andrei Kolmogorov）和格雷格里·蔡廷（Gregory Chaitin）独立发展了算法信息论（Algorithmic Information Theory，AIT），把可计算性与信息论深度融合：

柯莫哥洛夫复杂度：字符串 $x$ 的复杂度 $K(x)$ 是能输出 $x$ 的最短程序的长度。"随机"字符串就是那些没有比自身更短的描述的字符串。

这个定义让"随机性"有了精确的数学含义——一个字符串是随机的，当且仅当它不可压缩。大多数字符串（几乎所有足够长的字符串）是随机的；"有结构"的字符串（如 π 的前 100 万位）是可压缩的。

蔡廷的 Ω（Omega 数）是随机图灵机停机的概率，它是一个"完全随机"的实数——其二进制展开中没有任何规律，但它在数学上是完全确定义的。Ω 是数学中最具体的"不可知"对象之一：它存在，可以被定义，但其任意精度的值都无法被任何算法计算出来。

相对化与神谕#

可计算性理论的一个重要扩展是神谕机（Oracle Machine）：给图灵机添加一个"神谕"——能瞬间回答某类问题（如停机问题）的黑盒。

通过神谕机，可以定义相对化的可计算性层次：停机问题对普通机器不可判定，但对配备了停机问题神谕的机器则可判定——于是出现了第二层停机问题（配备神谕的机器的停机），以此无穷递进。这构成了可计算性的算术层次（Arithmetical Hierarchy）。

相对化技巧也在计算复杂性中发挥了重要作用：Baker-Gill-Solovay 定理（1975）证明，P vs NP 问题无法用"相对化"技术解决——即无法通过神谕机构造来证明 P = NP 或 P ≠ NP。这限制了一大类证明策略，提示 P vs NP 证明需要本质上新颖的数学技术。

跨域连接#

• 哥德尔不完备定理：两者用的是同一把刀。不完备定理构造一个"我不可证"的句子，停机问题构造一个"判定器说我停我就不停"的程序，都是让系统描述自身再取反。推论是形式系统的界不在算力而在自指：加公理、换机器、加纸带都消不掉这条对角线，只能把它挪到下一层重新出现。
• 数论：不可判定并非只发生在关于程序的问题上。判定整系数多项式方程有无整数解，这个纯数论问题被证明没有算法——于是"存在通用解法"在数学最古典的分支里也被否掉了。它同时说明界限落在哪里事先猜不出来：命题写得多朴素，与它可不可判定无关。
• 机器能思考吗：有人据此断言人心超越机器：人能"看出"某个不可证命题为真。这个论证的漏洞在于它默认人对自己所用形式系统的一致性有把握，而这恰是系统内部证不了的那一条。真要成立，得先证明人不是一个一致的形式系统，或者证明人可以是不一致的却仍然可靠。
• 形式化方法与验证：莱斯定理把不可判定推广到程序的任何非平凡行为性质。于是"完美查毒""判断两程序是否等价""保证永不崩溃"不是工程难题，而是不存在。现实工具只能退到保守近似：宁可误报，也不承诺完备——这条退让是被定理逼出来的。
• 量子计算理论：量子机器不越过这条线。它改变的是某些可解问题所需的资源等级，而非可解与不可解的分界——停机问题对它同样无解。把"更快"读成"能算更多"，是量子计算最常见的误解，也是判断一则量子宣称是否夸大的第一道筛子。

参考文献#

• Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proc. London Math. Soc. (1936).
• Church, A. An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics 58 (1936): 345–363.
• Sipser, M. Introduction to the Theory of Computation. 3rd ed. Cengage Learning (2012). （最广泛使用的教材）
• Davis, M. Computability and Unsolvability. McGraw-Hill (1958; Dover reprint 1982). （经典参考）
• Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatshefte für Mathematik und Physik 38 (1931). （不完备定理原始论文）