1936 年24 岁的英国青年艾伦·图灵提出了一台机器。这台机器没有任何零件、从未被真正造出来过——它只是纸上的一个抽象模型。可就是这台不存在的机器奠定了整个计算机科学的地基也划出了计算这件事的边界。今天你用的每一台电脑、每一个程序理论上都跑不出这台机器划定的范围。这篇文章就来讲这台机器——图灵机Turing Machine以及它揭示的那个令人震撼的事实有些问题永远无法被任何计算机解决。一台纸上的机器长什么样图灵想回答的问题特别本质“计算”到底是什么一个普通人拿纸笔能算的东西能不能用一个机械过程自动完成为了回答它图灵把人拿纸笔算题这个过程抽象成了一个极简的模型。一台图灵机就三样东西一条无限长的纸带被划分成一个个格子每个格子里写一个符号比如 0 或 1。纸带就是纸格子就是纸上的位置。一个读写头能看当前格子的符号也能改写它还能向左或向右移动一格。这就是眼睛和笔。一张状态转移表机器当前处于某个状态看到某个符号查表就知道——写什么符号、头往哪移、跳转到什么新状态。这就是计算规则。计算的过程就是机械地重复看当前符号 → 查表 → 写符号、移头、换状态 → 再看下一个符号……直到进入一个叫停机的终态停下纸带上留下的内容就是计算结果。听起来简单得有点寒酸可就是这个寒酸的模型能干你想象得到的一切计算——加减乘除、排序、下棋、训练神经网络理论上都能用一条纸带 一张规则表表达出来。图灵机为什么是计算的黄金标准图灵机提出后发生了一件让数学家惊讶的事别的模型算出来的东西跟图灵机一模一样。差不多同一时期数学家邱奇Church用完全不同的工具——λ 演算——定义了另一套可计算。结果发现图灵机能算的λ 演算也能算λ 演算算不了的图灵机也算不了。两个从完全不同的路出发的理论在什么是可计算这一点上精准地汇合了。这就是著名的邱奇-图灵论题Church–Turing Thesis一切直觉上可计算的函数都恰好是图灵可计算的函数。注意它是一个论题而不是定理——因为它涉及直觉上可计算这个无法严格定义的概念没法证明。但它经受住了近一个世纪的检验至今没有人找到人靠纸笔能算、但图灵机算不了的东西。从此可计算有了严格的定义能被图灵机在有限步内停机并给出答案的就是可计算的否则就是不可计算的。而图灵机之所以是黄金标准不是因为它快、它强而是因为它最简单——简单到足以作为所有讨论的共同地基。后来的冯·诺依曼体系结构、现代计算机本质上都是图灵机这个抽象模型的工程化实现寄存器是有限的纸带内存是那卷纸带CPU 的取指-译码-执行就是那套查状态转移表的循环。停机问题计算的边界在哪里既然可计算有了定义一个更尖锐的问题自然浮出水面是不是所有问题都能用程序解决图灵本人的回答是不是。而且他给出了一个漂亮到残酷的证明。他构造了这样一个问题叫停机问题Halting Problem能不能写一个程序输入任意程序 P 和它的输入 I判断 P 在输入 I 上最终会不会停机这个问题太实用了——你调试程序最想知道的往往就是它会不会陷入死循环。如果能写个万能检测器那 bug 就好找多了。但图灵证明了这样的程序不存在。证明的思路是经典的自指 反证特别精巧我给你讲直觉版假设真有这么个检测器H(P, I)能判断 P 在 I 上是否停机。那我们就能利用它造一个故意捣乱的程序D它调用H检查自己D(D)如果H说会停机那D就故意死循环如果H说不会停机那D就立刻停机。现在问D(D)到底会不会停机如果D(D)会停机那按D的定义H会说会停机于是D故意死循环——矛盾如果D(D)不会停机那H会说不会停机于是D立刻停机——还是矛盾。两个方向都矛盾说明前提错了那个万能检测器 H根本不存在。这就是自指的力量——它让程序去判断自己制造了一个无法自洽的逻辑死结类似于这句话是假话的经典悖论。“计算有边界”这个结论意味着什么停机问题的意义远超找不到万能 debug 工具这么简单。它宣告了一件事存在一些定义得清清楚楚的问题永远不可能有任何算法解决它。计算的疆域是有边界的边界之外是无能为力。而且停机问题只是一个开始。它打开了一扇门——可计算性理论数学家们据此给问题分了类哪些是可判定的、哪些是不可判定的、哪些是可计算但难到不可行的后者催生了后来的计算复杂度、P 与 NP 这类问题。你可能会问这跟我写代码、考研有什么关系关系大了。它给你的是一种思维上的清醒看到有人吹AI 无所不能你脑子里该有根弦总有些问题是任何智能包括 AI都无法用算法解决的这是数学上的硬边界不是算力够不够的问题面对一个难题你会先问这个问题本身可解吗而不是一头扎进去蛮干理解了计算的边界再看算法的效率大 O、复杂度才明白后者问的是另一个问题在可计算的范围内哪个算法算得最快。图灵机回答了能不能算复杂度理论回答算得有多快——这两层构成了计算机科学的理论根基。结语约束恰恰是创造的起点图灵机最打动我的不是它多强大而是它用一个极简到近乎简陋的模型抓住了计算最本质的内核一条纸带、一个读写头、一张规则表就足以定义全部的可计算性。它告诉我们两件事。第一真正的洞察来自做减法。图灵没有去造一台更快的机器而是把机器减到不能再减反而在最少里看清了最本质。第二承认边界不是认输而是清醒。停机问题说有些事做不成这不是坏消息——恰恰是知道了边界在哪我们才能把力气精准地花在边界之内可以做好的事情上。这跟做人做事是同一个道理。图灵机的可计算性再往前走一步就是算法——怎么把可计算的问题算得更快、更省。推荐 B站【408实验室】的《数据结构》从算法的复杂度、数据结构的组织讲起把这套计算的思维落到实处。