On Computable Numbers（图灵机 / 可计算性）

一句话

图灵为了回答希尔伯特的判定问题（Entscheidungsproblem），给「机械计算」下了第一个令人信服的精确定义——图灵机（Turing machine）；由此引出三件事：把每台机器编码成数据、造出能模拟一切机器的通用机（universal machine，现代存储程序计算机的蓝图）；用对角论证证明存在机器无法判定的问题；进而证明判定问题无解——一阶逻辑没有万能的判定算法。这篇论文同时奠定了「什么是算法」与「算法办不到什么」。

Glossary · 术语表

坐标

作者阿兰·图灵，写作时是剑桥国王学院 24 岁的研究员，论文 1936 年投出、1937 年刊于《伦敦数学会会刊》。它直接回应希尔伯特与阿克曼（1928）的判定问题，站在哥德尔不完备定理（1931）的肩上；几乎同时，普林斯顿的邱奇（Church）用 λ 演算独立得到了同样的否定结论（早图灵几个月）。图灵随后赴普林斯顿成为邱奇的学生，并在论文附录里证明了自己的「机器可计算」与邱奇的「λ 可定义」是同一回事。下启的是整个计算机科学——冯·诺依曼架构、可计算性理论、复杂度理论，源头都在这里。

问题与动机

二十世纪初，希尔伯特梦想把全部数学装进一套形式系统，再配一台「判定机」：任给一句数学命题，机械地走一遍就知道它真假可证与否。1931 年哥德尔证明任何足够强的系统里都有真而不可证的命题，击碎了「完备」这一半的梦。但还剩最后一问，即判定问题：哪怕系统不完备，有没有一套机械步骤，至少能判定「一个命题是不是逻辑上永真」？

要回答「有没有这样的机械步骤」，先得回答一个更隐蔽的前置问题：「机械步骤」到底是什么？只要「算法」还停在「凭直觉照章办事」的模糊状态，你就永远没法证明某件事「任何算法都做不到」——因为你根本没圈定「任何算法」是什么。这正是卡住所有人的地方。图灵的破局之处，是先把「计算」本身定义清楚，问题才第一次变得可证。

核心思想 / 方法

图灵机：把「计算」剥到骨头

图灵的出发点朴素得惊人：观察一个人（当年真管做计算的人叫「computer」）是怎么用纸笔算题的，再把无关的血肉全部剥掉，只留计算所必需的骨架。他的洞察是——人算题时，任一瞬间真正依赖的东西其实有限：眼睛只盯着纸上一小块、脑中只有有限个「心理状态」、每一步动作也只有有限种。把这些理想化，就得到一台机器：

• 一条向两端无限延伸的纸带，切成方格，每格写一个来自有限字母表的符号（可以空白）；
• 一个读写头，任一时刻只扫视一格，能读、能改写；
• 有限个内部状态（图灵叫 m-configuration，可理解为「机器此刻的念头」）；
• 一张死板的行为表（转移规则）：(当前状态, 读到的符号) → (写下某符号, 左移或右移一格, 切换到新状态)。

机器就靠反复查这张表往下走。为什么这样设计？因为它把「机械计算」压到了不能再省：无限纸带 = 不限量的草稿纸；一次只看一格 = 承认人的注意力有限；有限状态 + 有限规则 = 「照章办事、不靠灵感」。凡是能被任何明确算法算出来的，都能翻译成这样一张表。反过来，这台机器简单到可以拿它当「算法」的数学定义本身。

图灵这篇的字面目标其实是定义可计算数（computable number）：一个实数如果它的（二进制）小数展开能被这样一台机器一位一位地打印出来，就叫可计算。π、e、所有代数数都可计算。一台能永远打印下去、不卡死的机器，他叫它circle-free（无环）。

把机器编码成数字：可数 vs 不可数

关键的一跃：既然每台机器不过是一张有限的行为表，就能把它整个写成一串符号、再看成一个整数（图灵叫它「说明数 / description number」）。这一步看似记账小技巧，威力却极大。它意味着所有图灵机可以逐个编号：机器 1、机器 2、机器 3……——机器的总数是可数的。

可实数是不可数的（康托尔早已证明）。于是马上得到一个惊人的结论：绝大多数实数是「不可计算」的——它们的小数展开没有任何算法能生成。可计算数虽然囊括了我们叫得出名字的一切数，却只是实数汪洋里可数的一小撮。这也顺手把「机器无所不能」的幻觉先戳破了一半。

通用机：程序即数据

既然每台机器 M 都能写成一段数据（它的说明数），图灵便造出一台通用机 U：把「M 的说明书」连同 M 的输入一起写在 U 的纸带上，U 读一段、执行一步、再读一段……一步步把 M 模拟出来，算出跟 M 一模一样的结果。一台机器，喂不同的说明书，就成为任何一台机器。

这就是「存储程序」思想的数学原型：程序不再是硬接线的专用装置，而是和数据放在同一条纸带上、可以被读取和替换的符号串。今天每一台电脑——一块通用硬件，靠加载不同软件而变身相机、浏览器、游戏机——本质上都是图灵这台通用机的物理实现。十年后冯·诺依曼架构把它落地成真机器。

不可判定性：让机器审判它自己

有了能编号的机器和通用机，图灵抛出致命一问：能不能有一台机器 D，只看别人的说明数，就判定「那台机器是不是 circle-free（会不会永远算下去、还是终将卡死）」？他证明这样的 D 不存在，用的正是康托尔的对角论证。

直觉是这样的：假设 D 存在。那就能借它列出所有「乖机器」（circle-free 的），逐个编号，把它们打印出的无穷 0/1 序列排成一张无限大的表——第 n 行是第 n 台乖机器的输出。现在沿对角线取值、再逐位翻转，造一个新序列 β：它第 n 位故意跟第 n 台机器的第 n 位不同。于是 β 跟表里每一行都至少差一位，不可能是表中任何一台机器算的。可是——如果 D 真存在，「造 β」这套流程本身就是个算法，β 也该由某台乖机器算出、就在表里。它既在表里、又不在表里，矛盾。所以 D 不存在。

矛盾的根子是自我指涉：那台「造对角线」的机器最终会被要求算它自己那一位，于是陷入「要输出跟自己不一样的值」的死结——正是「这句话是假话」那种转不出去的怪圈。结论：存在机器判定不了的问题。（图灵原文说的是「circle-free 与否」不可判定；今天教科书里更常见的等价说法是停机问题（halting problem）：没有算法能对任意程序 + 输入，判定它会停下还是死循环。）

回击判定问题：一记归约

最后一步把机器的不可判定搬到逻辑上。图灵证明：任一台图灵机的运行，都能翻译成一句一阶逻辑命题——机器会怎样跑，等价于这句命题是否永真。于是倘若真有判定问题的万能算法（能判定任意逻辑命题永真与否），就能拿它去判定「机器会不会卡死」，可后者刚被证明不可判定——矛盾。所以判定问题无解：不存在能判定一切一阶逻辑命题的机械步骤。希尔伯特的最后一半梦，就此终结。

关键结果

这是一篇纯数学论文，没有实验，「结果」就是几条彼此咬合的定理：① 图灵机给出了「机械可计算」的精确定义；② 机器可逐个编号（可数），故绝大多数实数不可计算；③ 存在通用机，一台机器能模拟任何机器；④ 「机器是否 circle-free」不可判定（即现代停机问题的原型）；⑤ 由此判定问题无解。附录里他还证明「图灵机可计算」与邱奇的「λ 可定义」完全等价——两条截然不同的路，圈出的是同一片「可计算」疆域，这份巧合正是邱奇–图灵论题的证据。

为什么重要 / 影响

很难找到比它影响更奠基的计算机论文。它一次性交付了三块地基：其一，「算法 / 可计算」有了公认定义，理论计算机科学从此有了研究对象；其二，通用机 = 存储程序计算机的蓝图，「程序即数据、一机通用」的思想直接通向冯·诺依曼架构和今天的每一台电脑；其三，不可判定性划出了计算的绝对边界，衍生出停机问题、Rice 定理，以及「不存在完美的通用程序验证器、完美查毒引擎」等一整套「机器办不到什么」的结果。可以说，今天你能在一块芯片上装任何软件、也能证明某些自动化任务原则上不可能，两件事的根都在这 36 页里。图灵测试、人工智能是他后来的事，而计算本身的定义，就诞生于此。

局限与批评

• 邱奇–图灵论题是「论题」不是「定理」：「图灵机能算的 = 一切直觉上可机械计算的」这句话，涉及「直觉上可计算」这个非形式概念，无法被证明，只能靠证据支持（尽管几乎无人质疑）。
• 图灵机是定义工具，不是工程设计：无限纸带、一次挪一格，慢到荒谬，从没打算拿来真造机器。真机器来自 EDVAC / 冯·诺依曼一脉；这篇 1936 年论文对实际机器设计的直接因果影响有多大，史学界仍有争论（有人认为更多是事后追认的血统）。
• 原文有技术错误：图灵给出的机器描述（尤其通用机构造）相当繁复，含有 bug，靠 1937 年的更正说明及后人（如 Post）修补才完善——首篇之作并非无瑕。
• 只谈「能不能」，不谈「快不快」：可计算性是非黑即白的（可算 / 不可算），完全不涉及要花多少时间/空间。效率的世界（P vs NP、复杂度理论）是 1970 年代 Cook 等人另起的炉灶。
• 与物理世界的边界有争议：「物理可实现的计算是否也不超出图灵机」（物理版邱奇–图灵论题）、以及超计算 / 量子计算能否突破，属于持续的哲学与理论争论——不过量子计算改变的是效率，并不能算出图灵机算不出的东西。
• 优先权：邱奇用 λ 演算早几个月得到同一否定结论；只是图灵「模拟真人计算」的定义最直观、最有说服力，连哥德尔都认为它才真正说清了「机械步骤」。

要点