RezeのBlog
← 返回文章列表

停机问题

2024.03.24技术17993 字视频 6 · 参考 32

一九三七年,德国数学家考拉兹在课上提了一个游戏:随便取一个正整数,是奇数就乘三加一,是偶数就除以二,重复下去。

从七开始:七、二十二、十一、三十四、十七、五十二、二十六、十三、四十、二十、十、五、十六、八、四、二、一。回到一,停。

从二十七开始,要走一百一十一步,中途最高冲到九千二百三十二。

八十九年过去,没有人证明它对所有正整数都成立。二〇二〇年前后,计算机把范围验到了 2 的 68 次方,大约三万亿亿,仍然只是有限个例。

一个这么短的循环会不会停,人不知道。这是停机问题离得最近的样子。

但图灵问的不是这个。他问的是:有没有一个程序,给它任何程序、任何输入,它都能在有限步内答出「停」或「不停」,而且永远答对。

答案是没有。这个「没有」比考拉兹那个「不知道」强得多,也冷得多。

三段代码,八十九年

考拉兹那个游戏写成代码只有三行:判断奇偶,乘三加一或者除以二,回到开头。没有数组,没有递归,没有指针。

它至今是开问题。这类问题有个共同点:陈述短到小学生能听懂,证明难到没人做出来。

二〇一九年,陶哲轩发了一篇论文,证明在一种叫对数密度的意义上,几乎所有轨道最终都会被压到任意给定的界以下。

「几乎所有」这四个字要拆开看。它是一个密度陈述,不是「每一条」。剩下那些轨道会怎样,论文没有回答,也没有人知道。

这个例子用来说明一件事:判断一个只有三行的循环会不会停,可以难到让顶尖数学家停在这里。

但这仍然只是「不知道」。图灵的结论是「不可能有一个通用办法知道」,两句话差着一整个层级。

停机问题问的是什么

精确地写出来,停机问题是这个命题:存在一个程序 H,接受两个输入——一段程序 P 的描述,和一段输入数据 I——在有限步内输出「停」或「不停」,并且对所有的 P 和 I 都正确。

三个量词要摆清楚:一个 H,所有 P,所有 I。

否定也要摆清楚:对每一个候选的 H,都存在一对 (P, I),让它在有限步内给不出正确答案——要么答错,要么永远不答。

这句话里没有「时间不够」,没有「计算机不够快」,没有「人还不够聪明」。

H(P, I) = 1 若 P 在 I 上停机;H(P, I) = 0 若 P 在 I 上不停机

把 H 想成一个函数,定义域是所有程序与所有输入的配对,值域是 {0, 1}。它的存在性,就是全部问题。

注意这个定义的形状:它不在「难算」那一栏,在「有没有」那一栏。存在性和复杂度是两个不同的抽屉,这一点后面还要单独说一次。

跑起来看,只能得到两种答案

最朴素的办法是模拟:把 P 跑在 I 上,跑着看。

如果它停了,答案就是「停」,这个答案可靠,因为它已经发生了。

如果它没停,你只知道「到目前为止没停」。

跑了一亿步没停,可能第一亿零一步停;跑了一万亿步没停,可能第一万亿零一步停。步数没有上限,观察就没有终点。

所以模拟这个办法,能给出「停」,永远给不出「不停」。

这不是模拟不够努力。它拿到的信息本来就不够:它只见过有限个瞬间,而要下的结论是关于无限个瞬间的。

判定与半判定

把「能在有限步内给出答案」叫判定。把「答案为是的时候能给出答案,为否的时候可以永远沉默」叫半判定。

停机问题可以被半判定:跑,停了就说停。

它不能被判定。这是图灵的结论。

半判定还有一个等价的说法:可枚举。把所有会停的 (P, I) 配对排成一张表,存在一台机器能一行一行把这张表打印出来,只是每行的间隔不确定,顺序也不保证。

「能被打印出来」和「能被判定」是两件事。前者只要求存在,后者要求有尽头。

这个区别在实践里很实在:一个 bug 能被复现,不等于能证明没有 bug。

「再等等」有时候真的够用

有些情况下,「再等等」是有上界的。

如果事先知道「这个程序如果会停,一定在一万步之内停」,那么跑一万步就够了:停了是停,没停就是不停。

这个上界从哪来?有时候从结构来:一个只有 k 位内部状态的有限状态机,状态数是有限的,跑过状态数那么多步还没重复,就说明它永远不会重复,也就不会停。

有时候从数学来:循环变量每次至少减一,初值是 n,那就最多 n 次。

停机问题的困难,全在「没有这个上界」的时候。

反过来看,这句话很要紧:不可判定性藏在「任意长」这三个字里。一旦给一个上界,问题立刻变成可判定的——代价是答案变了,它回答的不再是「会不会停」,是「会不会在这个上界之内停」。

希尔伯特在博洛尼亚列的那张单子

一九二八年九月,希尔伯特在博洛尼亚的国际数学家大会上做了一场演讲,题目是《数学基础的问题》。

他列了几个问题,最后一个后来被叫作判定问题:是否存在一个机械的程序,对任意一个一阶逻辑的语句,能在有限步内判定它是否普遍有效。

同一年,他和阿克曼的《理论逻辑基础》出版,书里把这个问题的位置摆得更明确。

关键在于「机械的程序」这四个字。一九二八年,它没有定义。人们心里有一个模糊的图像:照着规则一步步做,不需要灵感,不需要判断。

这个模糊的图像就是后来所有麻烦的来源。要证明「不存在这样的程序」,先得说清楚「程序」是什么。

哥德尔先撞了一次墙

一九三一年,哥德尔在《数学与物理月刊》上发表《论〈数学原理〉及其相关系统中的形式不可判定命题 I》。

结论是:任何足够强、公理可枚举、一致的算术系统,都存在一个句子,它和它的否定都证不出来。

方法是对角线式的:把「可证明」这个元数学概念编码成算术谓词,再构造一个句子,它的内容恰好是「我这个句子不可证明」。

这个句子如果可证,系统就不一致;如果不可证,它就是真的但证不出来。

哥德尔没有回答希尔伯特那个问题。他证明的是「有些真句子证不出来」,不是「没有机器能判定所有句子」。

这两件事听起来挨得很近,实际隔着一层。要跨过去,得先有一台机器。

▶点击播放
毕导讲哥德尔不完备定理。算术化、自指句、可证与为真之间的那道缝,是停机问题出现之前的那一步。

图灵把「机械」变成了一台机器

一九三五年,纽曼在剑桥讲希尔伯特的判定问题。图灵听了这门课,随后开始想一件事:人做计算的时候,究竟在做什么。

他的做法和哥德尔相反。哥德尔从逻辑出发,图灵从动作出发。

他设想一个人,一支笔,一条无限长的纸带。纸带分成格子,每格写一个符号。这个人一次只能看一格,只能改一格,只能往左或往右挪一格。他脑子里记着有限条规则。

然后图灵说:凡是能这样一步步算出来的,就叫可计算。

论文一九三六年五月二十八日投给伦敦数学会,十一月十二日宣读,一九三七年印在会刊上。题目是《论可计算数及其在判定问题上的应用》。

这个顺序很关键:先有机器,才有「可计算」的定义;先有定义,才有「不可判定」的证明。

一台机器只有一张表

形式地写出来,一台图灵机是七样东西。

M = (Q, Γ, b, Σ, δ, q₀, F)

Q 是状态集,Γ 是纸带符号集,b 是空白符,Σ 是输入符号集,δ 是转移函数,q₀ 是起始状态,F 是停机状态集。

全部内容在 δ 里:读到某个状态和某个符号,决定写什么、往哪边走、变成哪个状态。

δ : Q × Γ → Q × Γ × {L, R}

没有内存,没有指针,没有函数调用,没有栈,没有堆。只有「读到什么、写什么、往哪走、变成什么」。

这台机器弱得可笑。但凡是「一步一步机械地做」能完成的事,都能编成它的转移表——这是图灵的论断,不是定理。

换一种机器,结论不变

有人会问:图灵机这个模型是不是太土了。只有一条纸带,一次只能动一格。换成多带、换成带随机访问的机器,会不会就能判定了。

不会。这些模型之间可以互相模拟。

多带图灵机可以把 k 条带子编码到一条带子上:用分隔符把各条带的内容隔开,再额外记下每个读写头的位置。模拟的步数会变慢,慢到平方级,但停不停不变。

带随机访问的机器,也就是平常说的内存模型,可以用图灵机模拟:把地址和数据编码在纸带上,来回移动读写头去找。慢,但能模拟。

非确定图灵机麻烦一点:每一步可以有多条转移,只要有一条路径能停就算停。模拟的办法是广度优先地搜索整棵计算树,一层一层展开。会停的机器迟早会被找到。

所以这些模型在「能不能算」这件事上是等价的,只在「算得多快」上不同。

这条性质叫模型无关性。不可判定性属于这一整类机器,图灵机只是最先被写下来的那一种。

反过来说,想绕开这条边界,只能造一个不能被图灵机模拟的东西。这正是「超计算」这个概念难的地方:你得先违反一条九十年来没有被违反过的经验规律。

通用机器

论文第六节,图灵做了一件当时没有人做过的事:把一台机器的转移表编码成纸带上的 0 和 1,然后写一台机器,读这段编码,照着执行。

这台机器叫通用图灵机,记作 U。它接受两个输入:一段描述,一段数据。

U 的存在意味着,机器可以读机器,也可以读自己。

这件事的意义超出了当时的语境:一台机器不必为每件事重新造,只要换纸带上的描述。九年后的 EDVAC 报告里,存储程序的想法被写成了工程方案。

对停机问题来说,U 提供了一样更紧要的东西:自指的可能。没有 U,就没有「把程序 P 喂给 P」这一步。

▶点击播放
图灵机的纸带、读写头、状态表。短片,把「一次只能看一格」这个限制演示得很清楚。

图灵当年问的不是停机

论文里图灵证的那个问题,比停机问题更窄。

他把机器分成两类:一类叫无环的,会无限地打印数字;一类叫有环的,打印有限个数字之后卡住。

第八节的标题是「对角线过程的应用」。图灵在那里证明:没有一台机器能判定任意一台机器是不是无环的。

然后他用这个结论去推判定问题:如果存在判定一阶逻辑的机械程序,就能用它判定无环性,矛盾。

「停机问题」这个名字是战后才通行起来的,图灵自己没有用过这个词。

今天教科书写成「给定 P 和 I,判定 P 在 I 上是否停机」,是因为这个版本更干净。它和图灵原来那个问题在可判定性上等价。

▶点击播放
从停机悖论推到不完备定理。两条路——哥德尔的算术化与图灵的对角线——在同一个地方会合。

同一件事的十几种外壳

停机问题有一批长得完全不像的亲戚。

  • 波斯特对应问题(1946):给一堆字符串对,问能不能挑出一组下标,让上下两行拼出同一个串。不可判定。
  • 王氏砖(1961):给有限种四边带颜色的方块,问能不能铺满整个平面。不可判定。
  • 希尔伯特第十问题:给一个整系数多项式方程,问有没有整数解。一九七〇年被证明不可判定。
  • 矩阵死亡率:给一组方阵,问能不能挑出一串相乘得到零矩阵。不可判定。
  • 生命游戏:给一个初始图案,问它最终会不会静止或进入周期。不可判定,因为这个游戏是图灵完备的。
  • λ 演算:给一个项,问它有没有 β 范式,也就是能不能归约到一个不再能归约的样子。不可判定。

这些问题的表面形式差别极大:一个是字符串,一个是几何铺砌,一个是数论,一个是矩阵,一个是元胞自动机。

共同点是它们都能编码「一台机器与一段输入」这一对东西。

所以证明一个新问题不可判定,有一个标准动作:把图灵机装进去。造一个实例,让它的解恰好对应某台机器的停机。装得进去,问题就不可判定。

这个动作在文献里出现了上百次,每次的翻译方式不同,骨架是同一个。

对角线

一八九一年,康托尔用对角线论证证明实数不可数。

结构是三句话:假设有一个完整的列表;从列表里构造一个不在列表里的东西;矛盾。

图灵把它从数搬到了机器上。

列表是这样的:第 i 行第 j 列写「第 i 台机器在第 j 个输入上停不停」。如果停机可判定,这张表就能被完整填出来。

然后沿对角线取反:造一台机器,它在第 i 个输入上的行为,和第 i 行第 i 列相反。

这台机器必须在表里,因为表号称完整。它又不可能在表里,因为它在每一列上都和对应的那一行不同。

对角线论证的力气全在「完整」这两个字上。它攻击的是所有列表的可能性,某一个列表反而不重要。

证明的五步

写成反证,五步。

第一步,假设存在 H。

第二步,构造 D:拿一段程序 P 的描述,问 H(P, P)。如果 H 说「停」,D 就进入死循环;如果 H 说「不停」,D 立刻停。

D(P) = 若 H(P, P) = 1 则 loop,否则 halt

第三步,把 D 的描述喂给 D 自己。

第四步,分两种情况。若 D(D) 停,则 H(D, D) 说停,于是 D 进入死循环,不停,矛盾。若 D(D) 不停,则 H(D, D) 说不停,于是 D 立刻停,停,矛盾。

D(D) 停 ⇔ H(D, D) = 0 ⇔ D(D) 不停

第五步,两种情况都矛盾,所以 H 不存在。

这个证明短到可以写在半张纸上。它没有任何深的技术,只有一次自指。

我认为它难懂的地方不在逻辑,在它的对象:H 是一个「能读任何程序」的程序,而人读这段证明的时候,脑子里那个 H 总会自动变成一个具体的、会出错的实现。一旦 H 变成具体的,矛盾就消失了,人就会觉得「那只是说明这个 H 不够好」。要挡住这个念头,得记住 H 是任取的。

▶点击播放
停机问题的动画讲解。反证、自指、D(D) 的两难,七分多钟能看完整套骨架。

同一年,大西洋另一边

一九三六年,邱奇在《美国数学杂志》第五十八卷上发表《初等数论的一个不可解问题》。

他用的是 λ 演算:一个只有变量、抽象、应用三样东西的系统。函数就是规则,应用就是代入。

他证明了同一件事:不存在一个递归的函数,能判定任意两个 λ 项是否等价,由此推出判定问题无解。

时间上邱奇更早。图灵的论文投出去的时候,邱奇的结论已经公开。

图灵随后在论文里补了一段,证明他的可计算数和 λ 可定义函数是同一类。

两个人在完全不同的形式系统里,划出了同一条边界。

论题不是定理

这三套定义——图灵机、λ 演算、一般递归函数——划出同一类函数。这件事本身没有定理的地位,是一个经验事实的重合。

邱奇-图灵论题说:能有效计算的函数,恰好就是图灵可计算的函数。

它不能被证明,因为「有效计算」没有形式定义。它是关于「机械」这个词该怎么用的主张,属于定义,不属于定理。

但它非常稳固。九十年里,量子计算、DNA 计算、神经网络、元胞自动机都被拿来试过,没有一个越过这条线。

量子计算能加速,能把某些问题的复杂度从指数压到多项式,但它能算的函数集合没有变。它是概率的、会出错的,可它跑不出可计算的范围。

这条论题的稳固,是后面所有结论的地基。哪天有人造出超越图灵机的计算装置,停机问题整座楼都要重画。

把问题变成一个集合

给每台机器编一个号。

办法很朴素:把转移表按固定格式写成 0 和 1,再把这一串当成一个二进制数。不同的机器有不同的号,虽然会有很多号对应不到机器。

用 φ_e 表示第 e 号机器算的函数。

停机问题就变成了一个集合:第 e 号机器在自己的编号上停机,这样的 e 收在一起。

K = { e : φ_e(e)↓ }

记号里的 ↓ 表示有定义、会停,↑ 表示不定义、不停。

这个集合里有一股自指的味道:第 e 台机器,输入是 e。

为什么可以把二元问题缩成一元?因为「P 在 I 上停不停」可以编码成一个数:把 (P, I) 配成一个自然数,造一台只在这个输入上模拟 P(I) 的机器。编号一改,二元就成了一元。

这一步看着只是记号的整理,实际是全部后续结论的支点:问题变成了一个自然数集合,集合就能和别的集合比大小、比难度。

K 可以被打印出来

有一台机器能做这件事:并行地模拟所有 (e, e),谁停了就把 e 打印出来。

并行的实现方式很土:第 n 轮,把前 n 台机器各推进一步。任何一台机器只要会停,它的停机会落在某一轮里,于是它的编号迟早会被打印出来。

这张表是无穷长的,打印的过程也是无穷长的,中间的顺序和间隔都不保证。

但「迟早会被打印出来」这一点是保证的。这样的集合叫递归可枚举,缩写 r.e.。

所以 K 是 r.e. 的。这是它最弱的性质,也是后面所有结论的起点。

K 的补集打印不出来

补集是那些「在自己编号上不停机」的机器。

假设补集也能被打印出来。那么把两台打印机并排放着,一台打印 K,一台打印 K 的补集。

给任意一个 e,盯着这两台机器看。e 只属于其中一边,所以迟早有一边会把它打出来。等它出现,就知道答案。

这样就得到了一个判定程序。可 K 不可判定。

所以补集不可枚举。

换个说法:证明「停」只要找到一次停机;证明「不停」要排除无穷多种可能,而这无穷多种可能没有一个有限的形状可以抓。

这个不对称在实践里天天出现:一个 bug 能被复现,说明程序有问题;可「没有 bug」这句话,永远没法用跑一次来证明。

三种语言

按「能不能判定」「能不能枚举」把问题分成三层,这是可计算性理论的基本地形。

可判定 定义:有算法在有限步内答是或否,例子:正则语言、括号配对、素数判定、Presburger 算术;可枚举不可判定 定义:有算法列出全部「是」,没有算法答「否」,例子:停机问题、一阶逻辑的有效式、丢番图方程有解;不可枚举 定义:连「是」都列不出来,例子:停机问题的补集。

这张表里有一个容易看漏的东西:中间那一行的三个例子看起来毫不相干,实际是同一类。

一阶逻辑的有效式可以被枚举:把所有证明按长度排,逐条检查,遇到能证明的公式就打印。这就是希尔伯特想要的那台机器的一半——它能认出定理,认不出非定理。

希尔伯特要的是一台能判定所有公式的机器。图灵和邱奇给的是:那台机器不存在,只有半台。

▶点击播放
「计算机不是万能的」这句话的准确版本:问题出在「有没有算法」,不在快慢。

可判定的那一侧也很宽

讲不可判定,容易给人一种印象:除了玩具问题,什么都判不了。实际情况不是这样。

  • 有限自动机:内存有限,状态数有限,跑过状态数那么多步必然重复,所以什么都能判定。
  • 下推自动机:多一个栈,仍然可判定。上下文无关语言的成员问题有 CYK 算法,时间复杂度是串长的三次方。
  • Petri 网可达性:可判定,一九八一年由梅尔证明,一九八二年科萨拉朱给出另一个证明。代价是复杂度到了阿克曼级,理论上能算,实际算不动。
  • 时间自动机:带时钟约束的有限状态机,可达性可判定,一九九四年由阿卢尔与迪尔证明。这是实时系统验证的理论基础。
  • Presburger 算术:只保留加法的自然数理论,可判定,一九二九年由 Presburger 证明。复杂度是双指数。
  • 实数闭域理论:塔斯基一九四八年证明可判定。复杂度同样是双指数,实际只能处理很小的式子。

规律很清楚:把「任意长的存储」或「任意嵌套的量词」剪掉一样,判定性常常就回来了。

但代价常常是复杂度爆炸。可判定不等于能算,这是第二层墙,比第一层更常挡住人。

一阶逻辑的有效性问题正好在边界上:命题逻辑可判定,加上量词和二元关系就不可判定。这条线细得像刀口。

归约

归约是这么一个动作:把问题 A 的每个实例改写成问题 B 的一个实例,使得答案相同。

如果 B 有算法,A 也就有算法;反过来,如果 A 没有算法,B 也没有。

A ≤m B:若 B 可判定,则 A 可判定

停机问题的地位高,是因为所有 r.e. 集合都能归约到它。

也就是说,任何「能被半判定」的问题,都可以改写成「某台机器会不会停」。

这叫 r.e.-完全。

有了这条,很多不可判定性就不用重新证了:把停机问题归约过去就行。丢番图方程有没有整数解,也就是希尔伯特第十问题,就是这么被证死的。一九七〇年,马蒂亚谢维奇,二十二岁。

赖斯定理

一九五三年,赖斯在《美国数学会会刊》第七十四卷上发了一篇三页的短文。

结论是:任何非平凡的、只依赖于程序所算函数的性质,都不可判定。

「只依赖所算函数」的意思是:两个程序写法完全不同,只要它们在每个输入上给出同样的输出,这个性质对它们就得一视同仁。

这样的性质,只要它不是「对所有程序都成立」,也不是「对所有程序都不成立」,判定它就不可判定。

举例:这个程序算的是不是常数函数;值域是不是有限;是不是对所有输入都有定义;是不是和另一个程序算同一个函数。

全部不可判定。

这条定理把停机问题从一个孤立的怪例,变成了一整片区域。停机只是这片区域里最方便下手的那个入口。

它和「难算」不是一回事

一个常见的混淆:把停机问题当成「很难算」,和旅行商问题排在一起。

它们不是一类。旅行商问题有算法,只是慢;停机问题没有算法,快慢无意义。

复杂度问的是「要多少步」,可计算性问的是「有没有有限步」。

这个区分在实践里有用:遇到一个慢问题,可以等更好的硬件;遇到一个不可判定问题,等多久都没用。

也有一个反过来的混淆:以为不可判定就意味着「什么程序都判断不了」。后面会专门拆这一条。

不可判定之上还有不可判定

图灵跳跃是一个操作:给定集合 A,把「第 e 台带 A 神谕的机器在 e 上停机」这个集合记作 A′。

神谕是一根凭空给出答案的线:机器可以随时问「这个数在不在 A 里」,一步拿到回答。

K 本身就是 0′。0 是空集,0′ 就是停机问题。

那么 0″ 是什么?是「给定停机神谕,判定带停机神谕的机器会不会停」。它也不可判定,即使 0′ 已经免费。

这个过程可以一直做下去:0‴、0⁗,无穷层。

所以停机问题不是最高的那堵墙,它是第一级台阶,往上还有无穷级。

算术层级

把「能用算术语言写出来的集合」按量词结构分层,得到的是同一件事的另一种画法。

Σ₁ 是形如「存在 y,使得 R(x, y)」的集合,R 是可判定的。

Π₁ 是形如「对所有 y,R(x, y)」的集合。

K 是 Σ₁ 完全的:它在 Σ₁ 里,而且所有 Σ₁ 集合都能归约到它。

「第 e 台机器在自己的编号上不停机」是 Π₁ 完全的,它是 K 的补集。

再往上一层:「第 e 台机器对所有输入都停机」,这一句要的是「对每个 x,都存在一个 s 让它在 s 步内停」,两个量词套着,是 Π₂ 完全的。

可判定的集合恰好是 Δ₁:能写成 Σ₁,也能写成 Π₁。

Δ₁ 形状:Σ₁ 与 Π₁ 都能写,例子:素数判定、括号配对;Σ₁ 形状:存在 y,R(x, y),例子:停机问题、丢番图方程有解;Π₁ 形状:对所有 y,R(x, y),例子:不停机(K 的补集)。

这张表和上一节的 0、0′、0″ 是同一件事的两种画法:一个用逻辑量词,一个用神谕。

同一条边界,可以从两个方向看见。

一个反直觉的推论

不可判定说的是「没有统一算法」,不是「每个实例都难」。

具体程序可以一个一个证。一个循环,只要找到一个每次严格下降且有下界的量,就证完了。

这与哥德尔定理的情形一样:每个命题未必不可证;不可有的是一个对所有命题都灵的办法。

数学实践里,人证出来的具体定理多得是。不可判定性从来没有阻止过任何一次具体的证明。

这句话值得说两遍,因为它是后面所有「工程上怎么办」的前提。

它和哥德尔定理谁更强

两个结论经常被并列提起,好像是一件事的两种说法。它们确实可以互推,但方向上有一个更直接。

从停机不可判定推到第一不完备定理,只要一句话。

假设有一个足够强、一致、而且完全的算术系统:每个句子要么可证,要么可证否。那么给定任意一对 (P, I),同时枚举「P 在 I 上停」的证明和「P 在 I 上不停」的证明,两边总有一边会先出现。这就给出了一个判定程序。

停机问题不可判定,所以这样的系统不存在。

反方向,从哥德尔推到停机,要多绕几步:得先把「可证明」编码成算术谓词,再用自指句构造矛盾。这条路哥德尔自己走了一遍,图灵换了一条。

所以在弱算术之上,两个结论是等价的。教科书常先讲停机问题,是因为它不需要算术化:只要一台机器,一次自指,半张纸。

这也解释了为什么计算机科学把停机问题当成自己的第一块界碑,而数学把不完备定理当成自己的。同一道墙,两个人从两侧各凿了一次。

忙碌的海狸

一九六二年,拉多在《贝尔系统技术杂志》上发表《论不可计算函数》。

他定义了一个数:n 个状态、两个符号的图灵机,从全零纸带出发,停机时最多能走多少步,记作 Σ(n)。

状态数是有限的,所以这样的机器只有有限台;每台要么停要么不停;停的那些步数有限。所以最大值存在,是一个确定的自然数。

Σ(n) = max { steps(M) : M 有 n 个状态,M 从全零纸带停机 }

但 Σ 不可计算。理由很短:如果能算 Σ(n),就能判定停机——给定一台 n 状态的机器,跑 Σ(n) 步,还没停就说明它永远不会停。

一个确定的、有限的、一行就能写出定义的函数,没有任何算法能算它。

这就是不可计算性最干净的样子:值在那里,只是没有任何办法拿到。

涨得比任何可计算函数都快

Σ 的增长有一个性质:对任何可计算函数 f,都存在一个 n,使得 Σ(n) 大于 f(n)。

「增长很快」不足以形容它。没有任何可计算的速度能跟上它。

已知的头几个值:Σ(1)=1,Σ(2)=4,Σ(3)=6,Σ(4)=13,Σ(5)=47,176,870。

前四个值很小,第五个突然到了四千七百万。看着像笔误,其实是函数从这一格开始露出了真面目。

有人拿它跟「谁能说出更大的数」这类游戏比。阿伦森写过一篇《谁能说出更大的数》,把这个函数当成一根标尺:你报一个可计算的构造,我用一个 Σ 压过去。

在这根标尺上,指数塔、阿克曼函数、葛立恒数,全都是可以被压过去的。

第五只海狸

一九九〇年,马克森和邦特罗克找到一台五状态机器,跑 47,176,870 步停机。这给出了下界。

要证明它是上界,得证明其余所有五状态机器都不会超过它,或者根本不停。

这一步卡了三十四年。

二〇二二年,特里斯滕·斯特林做了一个网站,把这件事拆成可以分给很多人的小块,叫忙碌海狸挑战。

二〇二四年七月,这个松散的团队宣布完成:枚举 181,385,789 台五状态机器,逐台判定,全部结论用 Coq 证明助手形式化验证。

参与者二十多人,大多数没有学术职位。

这是四十多年来第一次确定一个新的海狸值,也是第一个被机器验证过的海狸值。

第六只

六状态的情况完全是另一个样子。

已知的下界已经大到无法书写:某些六状态机器跑出的步数超过 10↑↑15,也就是十的十的十的……十五层。

而确切值可能永远不会被知道。

原因不是算力。五状态是一亿八千万台,人还能枚举;六状态的数量级到了千万亿,而且判定每一台所需的方法本身在变难。

更要紧的是,随着 n 增大,会有一批机器的行为独立于现有的公理系统:你既证不出它停,也证不出它不停,只能承认这个问题在系统之外。

这句话的具体形态,就是「不可判定」这四个字。

一个海狸值被算出来会怎样

海狸值不只是「谁能说出更大的数」这种游戏。它是不可判定性的一把尺子,量的是「要多少步才能撞到墙」。

Σ(n) 一旦知道,就能判定所有 n 状态机器的停机:跑 Σ(n) 步,没停就是不停。所以每确定一个 Σ(n),就有一整类机器被彻底解决。

二〇一六年,耶迪迪亚与阿伦森构造了一台 7910 个状态的图灵机,它的停机性独立于 ZFC。

构造的思路不复杂:让这台机器去搜索「ZFC 中关于某个命题的证明」,找到就停,找不到就永远找。如果 ZFC 一致,它就永远找不到,于是它不停;可这个「不停」在 ZFC 里证不出来,否则 ZFC 就证明了自己的不一致。

他们的论文还指出,某些中等规模的海狸值一旦被算出来,会顺带判定一批数论猜想。

这把「不可判定」从哲学拉到了具体的坐标:它不在无穷远处,就在七千九百一十个状态的那台机器上。

蔡廷常数

一九七五年,蔡廷定义了另一个数。

取一台通用机器,只考虑前缀无关的程序集:没有一个程序是另一个的前缀。给每个停机的程序 p 记一个权重 2 的负 |p| 次方,|p| 是长度。

把所有停机的程序的权重加起来,得到一个数,记作 Ω。

Ω = Σ 2^(−|p|),对所有停机的 p 求和

因为前缀无关,这些权重加起来不会超过 1。所以 Ω 是 0 和 1 之间的一个实数。

它的意义是:随机丢一段比特给这台机器,它停下来的概率。

知道 Ω 的前 n 位,就能判定所有长度不超过 n 的程序是否停机。理由:把长度不超过 n 的程序按权重从大到小排,累加到超过 Ω 的前 n 位为止,剩下的都不可能停机。

所以 Ω 不可计算。而且它不只是不可计算,它是「随机」的:二进制展开里没有任何可以利用的规律,任何一段都不比它本身短多少。

一个确定的数,每一位都存在,写在 0 和 1 之间,没有一位能算出来。

柯尔莫哥洛夫复杂度

同一件事的另一个说法:一个串的复杂度,是能输出它的最短程序的长度。

K(x) = min { |p| : U(p) = x }

K 不可计算。否则就能判定停机:给一段程序,算它输出串的复杂度,再比长度。

但 K 有上界:任何压缩算法给出的都是上界。gzip 压完的长度,就是一个不超过原长、也不超过 K(x) 加某个常数的数。

有一个漂亮的结论:几乎所有的串都不可压缩。长度 n 的串有 2 的 n 次方个,而长度小于 n 的程序不到 2 的 n 次方个,鸽笼一放就出来了。

所以「随机」在大多数情况下是默认状态,不是例外。

它没有说的四件事

这个结论被引用得太顺口,所以先把它没说的部分列清楚。

  • 不是「程序的行为无法预测」。具体的程序可以分析,可以证明,可以测试。不可判定的是「对所有程序都有办法」这个要求。
  • 不是「计算机不够快」。给无限的时间、无限的存储,照样不行。它不在速度那个维度上。
  • 不是「有些程序能判断,有些不能」。准确的说法是:没有一个程序能对所有程序都判对。任何具体的判定器都会在某一类输入上失败。
  • 不是「程序验证没有意义」。验证一个具体程序,和判定所有程序,是两件不同的事。前者每天都在做成功。

这四条里,第一条和第四条最常被混在一起。区分它们的办法很简单:看句子里有没有「所有」。

可靠与完备,只能选一个

一个分析器有两个理想性质:可靠,说停就一定停;完备,凡是会停的都能认出来。

停机问题说:对一般程序,两者不能同时有。

这里有一个很强的反驳,值得先摆出来:既然两者不能兼得,那整个静态分析这一行是不是在白费力气?毕竟分析器给出的「不知道」,对写代码的人没有任何帮助。

我的判断是:这个反驳把「一次性判定」当成了唯一有用的形式。实际的分析器更像筛子,不做判定,做筛选:把大部分明显安全的代码筛出去,把可疑的留下。留下的那部分再由人来判断,或者由测试来覆盖。

换句话说,它的价值不在答案,在减少需要人看的东西的数量。一件工具每天替你划掉九十行,剩下十行你亲自看,这就够了。

所以现实里的分析器一律选可靠,放弃完备。结论有三种:停、不停、不知道。

不知道是设计里留好的位置,不算失败。

抽象解释

一九七七年,库佐和库佐在 POPL 上发表《抽象解释:一种统一的格模型》。

思路是把具体的值映射到一个有限的抽象域里:区间、符号、多边形、整除性。

在这个抽象域上定义一套对应的运算,然后做不动点迭代:从一个粗略的估计出发,反复应用,直到不再变化。

因为抽象域的高度有限,或者用了加宽算子强制收敛,迭代必然在有限步内停下。

停机问题就这样被降级了:从一个关于任意长运行的问题,变成一个有限格上的收敛问题。

代价是过近似:得到的是包住真实行为的一个更大的集合,所以会出现「明明是安全的,分析器说不知道」。

航空电子的静态分析工具 Astrée 用这套办法,证明了空客 A380 的飞控代码没有运行时错误。它证的是一个具体程序,不是所有程序。

Terminator

二〇〇六年,微软研究院的库克、波德尔斯基、雷巴尔琴科在 PLDI 上发表《系统代码的终止性证明》。

工具叫 Terminator。它做的事:给一段 C 代码里的每个循环找一个 ranking function,一个每次迭代都严格减小、并且有下界的量。

找不到就换一个,再找不到就说不知道。

它证过 Windows 内核里的一些循环会停。这些证明有实际的用处:一个不会停的内核循环,在驱动出错的时候会把整台机器挂住。

但它从来不说「这段代码一定不停」。它只有「证完了」和「不知道」两种输出。

这就是停机问题在日常工程里的真实形态。

证明终止的三种形状

工程上证明一个循环会停,反复出现的只有三种形状。

第一种,递减计数器。从 0 到 n 的循环,n 减 i 是一个非负整数,每轮严格减小。它不可能无限下降,所以循环必然结束。

第二种,词典序。两层嵌套循环,外层的下降次数取决于内层跑了多少轮。单看外层变量,它可能不变;把两个变量配成有序对,按字典序比较,每一轮严格下降。自然数对的字典序是良基的,所以还是会停。

第三种,测度函数。快速排序的递归,用的是待排序区间的长度;并查集的路径压缩,用的是树高的上界;图的遍历,用的是未访问节点数。共同点是它们都是自然数,每轮严格减小。

三种形状背后是同一个事实:自然数不可能无限下降。终止性证明的全部内容,就是找一个从程序状态到自然数的映射,让每次迭代都把它压小。

这也是为什么这件事在实践中常常可行:人写循环,本来就是为了让它停,结构里天然带着那个量。找它比造它容易。

反过来说,凡是你找不到这个量的循环,最该做的事是加一个计数器上界,把它换成一个可判定的问题。

用更小的语言换可判定

另一条更彻底的路:不用通用语言,用特意做小的语言。

  • 正则表达式:每次读一个字符,位置只前进,步数不超过串长,必然停。
  • Datalog:变量只取有限域里的值,规则单调,不动点必达。
  • Starlark:Bazel 的配置语言,规范里写明不做图灵完备,所以配置文件一定能读完。
  • Dhall:总函数语言,规范保证每个程序都终止。

这些语言的共同点:放弃「什么都能算」,换来「一定能结束」。

SQL 是反面例子。加了递归 CTE 之后它是图灵完备的,所以一个递归查询可能永远跑不完。很多数据库因此加了递归深度上限——又是那个「加上界」的动作。

这条路线里有一个容易忽略的代价:语言小了,表达力就小,很多本来直接能写的东西得绕着写。配置语言尤其明显,用户第一反应通常是「为什么这里不能写个循环」。

总函数语言的税

Coq(现在叫 Rocq)和 Agda 是证明助手,它们的核心语言里每个函数都必须是全函数。

因为要保证「证明检查一定能结束」,就不能允许一个定义在检查过程中跑不完。

但终止性一般不可判定,所以检查器只能保守:它用结构递归、守卫条件、大小变化这些可判定的充分条件。

后果是有些明显会停的程序写不进去。你得把它改写成检查器看得懂的形状:加一个递减的计数器,或者换一种递归结构。

这是每天都能感觉到的税。停机问题在类型论里的具体价格,就是程序员多写的那些辅助参数。

也有绕开的办法:把函数标成 partial,放弃保证。可一旦放弃,用它写的证明也就不再可靠,检查器不再替你背书。

Lean 走的是同一条路,只是野心更大:它想把大量现成的数学搬进这套体系里。能进库的每一步,都得先过终止性这一关。这条路线在构造性数学里有更长的传统——不接受排中律的人,本来就更在意「算得出来」这件事。

借还检查为什么算得出来

Rust 的借用检查曾经是词法的:一个引用的生命周期到它所在的块结束。

后来改成非词法生命周期:生命周期由一组约束决定,求解这组约束是一个不动点计算。

约束图画在程序的区域上,区域的数量有限,约束是单调的,所以迭代一定收敛。

这是又一次「把不可判定压成可判定」:不问「这段程序会不会出错」这种一般问题,只问「这组具体的区域约束有没有解」。

代价同样在表达力上。有些明显正确的程序过不了检查,得重写成检查器喜欢的样子,或者写 unsafe。

这个交易是明码标价的:拿掉一整类内存错误,换掉一部分写法的自由。

加一个上界

前面埋的那句话,在这里收回来。

「程序会不会停」不可判定;「程序会不会在十亿步内停」可判定——跑十亿步。

工程上所有超时机制都是这个变换:网络请求的超时、数据库的查询超时、Kubernetes 的存活探针、看门狗定时器。

它们回答的是「会不会在期限内完成」;「会不会完成」这个问题,没有人真的在问。

这个变换看起来像逃避,其实是把问题换成了一个有答案的问题。工程上要的本来就不是那个形而上的答案。

我的判断:停机问题对写代码的人最有用的一课,是「说清楚你到底在问哪一个问题」;「有些事做不到」反而次要。

C++ 把问题定义掉

还有第三种处理方式:不改问题,改「什么算合法程序」。

C++11 起有 forward progress 保证:一个没有副作用、没有同步操作、不会终止的循环,是未定义行为。

编译器因此可以假设循环会结束,从而把后面的代码搬来搬去、删掉。

这条规则在标准里写得很干,但它是一次明确的取舍:为了让优化有依据,把「永远不停」从合法程序里划出去。

同样的思路在别处也有:Java 的内存模型要求每个线程最终要前进,编译器才能做某些重排。

三种办法摆在一起看很清楚:加时间界、限制语言、改定义。三种都在绕开停机问题,没有一种在解决它。

病毒检测

一九八六年,弗雷德·科恩在 USC 写完博士论文《计算机病毒》,次年在《计算机与安全》上发表了实验部分。

他给病毒下了一个基于行为的定义:一段能修改其他程序、把自身或其变体植入其中的程序。

然后他证明:精确判定一个程序是不是病毒,不可判定。论证方式是把停机问题归约过来:造一个程序,它先模拟某台机器,那台机器停机就发作,不停就什么都不做。

所以杀毒软件只能做近似:特征匹配、行为启发、沙箱里跑一会儿。

它们全都可能漏,也全都可能误报。这不是厂商不努力。

AI 也绕不过去

大模型能读代码、能补代码、能解释代码。有人由此推想,哪天它就能判断任意程序会不会停。

不能。这道墙的位置不在智能程度,在量词。

一个人或一个模型可以对某一个具体程序给出正确的判断,甚至给出证明。但「对所有程序都正确」这个要求,是一个关于所有可能程序的全称命题,而所有可能程序的数量是无穷的,它们的描述又能互相编码。

一个模型可以越来越准,但它给出的永远是判断,不是保证。要保证,就得回到证明:给一个 ranking function,给一个不变式。

这不是给 AI 泼冷水。它说的是:有些工作的价值在于给出理由,而不在于给出答案。

▶点击播放
关于「AI 能不能突破 1936 年那个证明」的讨论。结论不难,难的是说清楚它为什么和模型大小无关。

一张地图

停机问题常被讲成一句绝望的话:有些事永远做不到。

它更像一张地图:标出哪些问题有算法,哪些没有,哪些有但代价高,哪些有但要限制语言。

这张地图上有几块清楚地界。

  • 可判定:正则语言、上下文无关语言、Presburger 算术、实数闭域理论。最后两个可判定,但复杂度是双指数级的,理论上有算法,实际算不动。
  • 可枚举不可判定:停机问题、一阶逻辑的有效式、丢番图方程有解、波斯特对应问题。
  • 不可枚举:停机问题的补集。

验证这条路上有两个常被举的例子:CompCert 把 C 编译器本身的正确性证了一遍,seL4 把一个微内核的功能正确性证了一遍。两个都是了不起的工程,但它们证的都是具体的程序,不是所有程序。

地图的价值在于,走到边缘的时候你知道自己在边缘,不会把力气花在凿一堵没有门的墙上。

反过来,地图也标出了可以凿的地方:把语言改小、加上界、只证具体实例。这三条路都不在「不可能」的区域里。

回到那半张纸

再看一遍那个证明。它只用了两样东西:一台能读程序的机器,和一次自指。

两千年里,数学家一直在造越来越强的工具。图灵做的是相反的事:他造了一台弱到不能再弱的机器,然后证明这堵墙就在这么弱的地方。

强不强不影响墙的位置。这是我认为这个结论最反直觉的地方:问题不在计算机够不够好,在「计算机」这个概念的形状本身带着一条边界。

落到日常,只有一个动作:写循环的时候,能说出它为什么停——一个严格递减的量、一个必然被消耗的输入、一个必然缩小的区间。说不出来,就加一个上界。

上界不是认输。它把「会不会停」换成了「会不会在期限内完成」,而后者有答案。

停机问题讲了九十年,最后留在手里的,是这个动作。

参考