人是机器吗 — 人工智能的计算理论基础
这一章讲三件事: "人是机器吗"这个古老问题怎么被逐级归约成可讨论的形式—— 人是不是可计算的(丘奇-图灵论题层面)、人是不是可高效计算的(复杂性层面); 图灵机这个"直觉上最简单、最可靠"的装置到底怎么工作(主走查:二进制加一); 以及所有试图越界的挑战者——超计算、BSS 实数模型、量子计算——各自的真实成色。 原书作者在前言里说读者可以跳过这一章1;我们的立场相反:这是全书唯一一章 能回答"AI 的天花板在哪"的,值得慢读。
1. 这一章讲什么
原书把这个问题处理成一条归约链2:
人是机器吗?
↓ (按冯诺伊曼的说法,神经系统的本质是数字的;费曼:世界是数字的)
人是计算机器吗?
↓ (离散的量上,二进制就足够)
人是数字计算机吗?
↓ (如果把"智能"当作人类特有的性质)
机器有智能吗?
归约的好处是把玄学变成技术问题。 "灵魂""自由意志"吵不出结果; "是否存在一种计算装置,能模拟人的全部行为"可以。而要回答它,需要两个不同层面 的理论——原书的分工极其清楚3:
| 层面 | 理论 | 回答的问题 |
|---|---|---|
| 可计算性 | 丘奇-图灵论题 | 能不能算出来(原则上) |
| 计算复杂性 | 相似性原则 | 能不能用多项式规模的算力算出来(现实中) |
2. 顶层全景
1936 图灵《论可计算的数》:定义图灵机;丘奇 1937 年书评命名"图灵机"
↓
互相模拟:递归函数 ≡ λ演算 ≡ Post系统 ≡ 图灵机 ≡ 细胞自动机
↓
丘奇-图灵论题:所有足够强的计算装置都等价于图灵机(观察,不是定理)
↓
UTM(万能图灵机):程序可被编码为数据 → 存储程序 → 冯诺伊曼架构
↓
复杂性层:多项式=小,指数=大;P 对 NP(库克 1971,源自定理证明)
↓
相似性原则(洪加威):靠谱的计算装置互相模拟只差多项式 = 强丘奇-图灵论题
↓
挑战者:
· 超计算(oracle)——理论方便,无物理实现
· BSS 实数模型——数学好用,物理存疑
· 量子计算——复杂度层真有优势(肖尔),可计算性层无越界
↓
结论:认可两个论题 ⟹ 人就是图灵机;"超级智能"要么是更快的图灵机,
要么预设了超计算——原书称后者为模糊不清的伪概念
图说:主走查在第 3.2 节(图灵机加一);每个挑战者的"成色鉴定"在第 3.6 节。
3. 核心原理
3.1 图灵机:三个部件,没有任何魔法
图灵 1936 年的初衷是让机器模仿人类计算者——那时 computer 一词指人类计算者 (通常是女性),按算法设计师的指令执行计算步骤4。所以图灵机的构造就是把 "一个人拿纸笔按规则算数"拆到不能再拆:
- 一条无穷长的纸带,分成格子,每格写 0 或 1(纸+笔迹);
- 一个读写头,读当前格子、写 0 或 1,可左移右移一格(眼睛+手);
- 一个有限状态自动机,根据"我现在的状态"+"当前格子是什么",决定写什么、 往哪移、进入什么新状态(脑子里的操作规程)5。
它为什么强大?恰恰因为简单。 哥德尔本来对自己定义的递归函数是不是"最广义的 计算装置"不自信,看了图灵机的构造后完全信服5。
3.2 主走查: 一台图灵机做二进制加一
拿最小的实用任务走一遍:把纸带上的二进制数 101 加一,得 110。 机器的规则表(规则集为教学而简化,与标准构造一致):
状态:q0(向右找数尾)、q1(向左进位)、H(停机)
记号:读写头停在哪个格子,用 [ ] 括住
规则:
q0: 见 0/1 → 原样重写,右移 (先走到最右)
q0: 见 □(空格)→ 写 □,左移,转 q1 (过了数尾,回头加一)
q1: 见 1 → 写 0,左移,留在 q1 (1 加 1 进位,本位变 0)
q1: 见 0 → 写 1,左移,转 H (0 加 1 变 1,进位结束)
q1: 见 □ → 写 1,转 H (一路进位到头,扩一位)
执行(每个状态旁标注当时的纸带与读写头):
q0 [1]0 1 读 1,重写,右移
q0 1[0]1 读 0,重写,右移
q0 1 0[1] 读 1,重写,右移
q0 1 0 1[ ] 读空格,左移,转 q1
q1 1 0[1] 读 1 → 写 0,左移(进位!)
q1 1[0]0 读 0 → 写 1,左移,转 H(进位结束)
H 1[1]0 停机。纸带上是 110 = 6 ✓
图说:全程只有"看一格、写一格、移一格、换状态"四种动作。
没有加法器、没有乘法器——二进制加一是被这套裸动作"走"出来的。
任何计算,从手 机解锁到训练大模型,原理上都可被这一套动作模拟,
区别只是快慢。
这个走查解释了两件事。 第一,为什么"人是机器吗"可以认真讨论:如果思维也是 某种"读-写-移-换状态"的过程,图灵机就是它的极限形式。第二,为什么效率是 另一个独立问题:上面 7 步算 5+1 很可爱,但同样这套动作模拟一次大模型推理, 按天文数字的步数计——快慢的问题,交给下一节。
3.3 丘奇-图灵论题:一条"观察",不是定理
论题内容:所有功能足够强的计算装置,计算能力都等价于图灵机。
原书对它的定性必须原样保真:"这是一个观察,而不是定理"——图灵、丘奇、克里尼 等人证明了当时所有数学家想出的装置(递归函数、λ演算、Post 系统、图灵机)互相 可模拟;"这是归纳,不是演绎,所以这不是数学定理,更像物理定律"7。 无法严格证明的原因:没人能保证未来不会发明新的计算装置。 但"那么多最聪明的人想出来的玩意都是等价的"确实给了信心:这些就是最强的装置7。
三个值得一记的考证(原书的闲笔,其实都是大历史):
- "图灵机"这个名字是丘奇起的:1937 年丘奇在《符号逻辑杂志》书评里首次使用;
- λ 的记号来自排版事故:罗素的"戴帽"记号 x̂ 排不出,排字工用大写 Λ 顶替, 后来演变成 λ——"本应称作丘奇演算的东西,阴差阳错成了 λ演算"8;
- 万能图灵机(UTM)是软件产业的源头:一台图灵机的执行过程可被编码成数据放上 纸带,另一台图灵机读出来逐步执行——"被编码的图灵机就是软件"; 冯诺伊曼架构的核心思想"存储程序"即源于此(冯诺伊曼架构真正的原创是随机寻址, 那是工程考量;冯诺伊曼本人把原创思想的功劳都给了图灵)9。
3.4 复杂性层:"大"和"小"是难定义的
可计算性回答"能不能",复杂性回答"多贵"。 而先要定义什么是"贵得可以接受"。
原书用王浩悖论展示这个定义有多微妙:"1 是小的数;如果 n 是小的数,那么 n+1 也是小的数"——按数学归纳法,岂不是所有自然数都是小的数?10 悖论的解法是 约定一个分界。计算复杂性理论的约定:多项式时间=高效(小),指数时间=低效(大)。 理由不是哲学,是增长速度的可控性:多项式随规模放大得慢,指数呈爆炸。
原书还补了两个诚实的脚注:最坏情况不等于日常(快速排序最坏 n²、日常飞快; 单纯形法最坏指数、日常好用),所以有"平均复杂性分析"11。
在这个坐标系里放两个明星问题12:
次走查:TSP(旅行商问题)——给 n 个城市,找一条最短的回路。
求解:要检查的回路约 (n-1)!/2 条。n=20 时约 6×10^16 条;
每秒核对 10 亿条,也要约两年;n=30 时宇宙年龄不够用。
验证:给我一条具体路线,把 20 段距离相加、比一下已知最优——
约几十次加法,瞬间完成。
图说:"求解贵、验证便宜"的落差,就是 P 对 NP 的全部直觉。
NP 完全问题是 NP 里最难的那批;第一个 NP 完全问题(SAT)是库克 1971 年
在研究机器定理证明时发现的(第 02 章的人物在这里重逢)。
P 是否等于 NP 至今无解,在斯梅尔 18 问题表和克雷七题里都排第三。
原书由 P≠NP(若真如此)推出两条生活化推论:证明一个定理比验证这个证明要难, 写书比读书要难12——复杂性理论第一次给"创作比批评难"提供了数学表述。
3.5 相似性原则:复杂性层的"强论题"
丘奇-图灵论题说大家能力等价,但模拟的成本呢? 会不会存在一种装置, 算同样的事比图灵机快得多?这就是 80 年代洪加威提出的相似性原则: 计算装置之间互相模拟的成本是多项式的——靠谱的计算装置之间,不存在 原则性的效率差异13。
它又称"强丘奇-图灵论题"或"扩展的丘奇-图灵论题",与丘奇-图灵论题一样是观察 而非定理。原书交代了它被"渐渐淡忘"的原因:它已经变成计算理论的工作假设, 大家习以为常;而"如果相似性原则不成立,那么大部分算法复杂性的成果就要被推翻了"13。 理论计算机科学家阿伦森甚至认为,复杂性比可计算性"有更多的哲学含义"14。
到这里,原书给出了本章(也是全书)最硬的一句话:"如果我们认可丘奇-图灵论题 和相似性原则,那么人就是图灵机。目前的所有人工智能工作都是建立在这个认同之上的。"15
3.6 越界者鉴定:超计算、BSS 与量子计算
超计算(hypercomputation):图灵研究专家寇普兰的术语,指可计算性上超越 图灵机的装置——注意与"超级计算"(supercomputing,算得多的普通机器)是质变与量变 之别16。图灵本人设想过"oracle"(一台图灵机可以询问一个更强的外部装置), 但具备超计算能力的 oracle 没有物理实现。原书作者自己补了一条判据: 在复杂性层面不服从相似性原则(能模拟但不能多项式模拟)也算超计算; 有人的评价是:遵从两个论题的话,超计算"就是类似永动机的东西"17。
BSS 实数模型:布卢姆、沙布、斯梅尔三人提出的计算模型,核心假设是 任意精度(想要多少位就能算到多少位)的实数四则运算,都可以在单位时间内完成。它是数值算法分析的好工具, 但在 BSS 模型里一阶实数理论可判定(正是塔尔斯基定理的计算体现,与图灵机上 整数算术不可判定形成镜像)18。它的成色:数学上好用,物理上存疑—— 没有人知道怎 么造一台"实数运算零成本"的机器;按费曼"宇宙是数字的"的判断, 它更像模拟计算模型的数学影子19。
量子计算:成色最微妙的一位。可计算性层面它不越界——量子计算机不能求解 图灵机不可计算的问题,某种意义上它符合丘奇-图灵论题;但在复杂性层面,它可能 与相似性原则冲突:素数分解在图灵机上被认为很难(RSA 的 1024 位密钥,朴素筛法 约 2^512 次运算;即使用最快的已知算法仍是指数级),1994 年肖尔给出了量子计算机上 的高效算法;2001 年 IBM 用 7 个量子位把 15 分解为 3×520。怀疑者(列文、 古德瑞克)认为实用的大规模量子机造不出来;原书的中性判断是: "实用的量子计算机是有可能实现的"21。
原书给三位挑战者的总评一句话:超计算无实现、BSS 无物理、量子计算不越可计算性 之界——图灵机的王座至今无人撼动,能撼动的只剩"效率"这一个方向。
3.7 哲学寓意:三层楼梯与两个跳跃
理论的用处在于给争论分级。原书给 了两副阶梯:
马尔的视觉三层22:计算层面(解决什么问题)↔ 丘奇-图灵论题; 算法/表示层面(怎么算)↔ 相似性原则;物理实现层面(怎么造)。 瓦连特的三层23:超级普适性(计算模型,如图灵机)→ 普适性(如 NP 完全性 理论)→ 数学结论(具体某问题的复杂性)。底层变,上层跟着变:若计算模型换成 量子计算机,复杂性理论就换成 BQP 之类。
用这两副阶梯看反 AI 阵营,原书借多依奇之口说了句公道话:只有彭罗斯"抓到了 点子上——反对人工智能必须从推翻丘奇-图灵论题下手";彭罗斯的路线是人脑有量子 效应,所以思维可能超越图灵机。原书指出其中藏着两个跳跃:图灵机到量子计算的 跳跃、量子计算到人的跳跃——每一跳都需要证据,目前都没有24。
至于"超级智能",原书的判词毫不客气:"目前声浪很高的'超级智能'是个模糊不清的 伪概念"——若认可图灵机等价于智能,超智能要么是更快的图灵机(摩尔定律+算法 就能到),要么预设了超计算(未证明存在)25。
4. 作者的判断与 证据
史实层:图灵机定义、各装置等价性定理、库克-列文定理、洪加威的原创论文、 肖尔算法与 IBM 2001 年的 7 量子位实验,均有文献。
作者观点层(这一章作者亲自下场最多):
- "计算理论的一些基本道理应该像牛顿定律一样,写到中学教科书里"(第 3 版前言), 并自称计算理论是"最具第一性原理的理论,甚至比理论物理学更为基本"26;
- 作者提出"超计算"的复杂性判据(3.6 节),这是他本人的学术主张;
- "现在跟风搞深度学习的人,大多数压根就没听说过丘奇-图灵论题"——对从业者的 批评,呼应第 12 章"教科书缺第一性原理"的判断27;
- 高德纳"计算机科学是非自然科学、每 50 人里 1 人具备这种思维方式"为原书引用28, 不是作者原创。
原书标注存疑处:量子计算的实现时间表各方分歧巨大,原书只引了正反两方 (支持者与列文/古德瑞克的怀疑),不给预测21。
5. 边界与局限
- 本章是浓缩版教程,不是教材:可计算性理论(停机问题——判断一段程序会不会永不停——、归约)、复杂性类的 包含关系(NP⊆PSPACE 等)原书只点名不展开;要系统学习看计算理论教材 (原书参考文献指南推荐了 Arora 与 Sipser)。
- "相似性原则"的表述在不同文献里强弱不同,原书取的是洪加威原文的版本; 阅读其他材料时注意术语叫法是否一致。
- 量子计算进展极快:原书的快照停在肖尔算法与 7 量子位演示;2024-2026 年的 纠错进展请以最新资料为准。
- "人就是图灵机"是一个条件句:它的前提(两个论题)不可证明——这是原书 诚实的立场,不要把条件句读成断言。
6. 可带走的
- "人是机器吗"有一条归约链:人→计算机器→数字计算机→机器有智能吗; 归约把玄学变成可讨论的技术问题;
- 图灵机 = 纸带 + 读写头 + 状态表,全程只有读、写、移、换状态四种动作; 它的强大来自极简——简单到无法再拆,也就无法再被反驳;
- 丘奇-图灵论题是"观察",更像物理定律:所有足够强的计算装置都被证明互相 等价,但无法排除未来出现新装置;
- 万能图灵机 = 程序即数据:软件产业和存储程序架构的理论源头,1936 年;
- 可计算性与复杂性是两层独立的问题:能算 ≠ 算得动;相似性原则说, 靠谱的装置之间连"快慢"都没有原则差异;
- P 对 NP 的直觉:求解贵、验证便宜——"证明定理比验证证明难,写书比读书难";
- 量子计算不越可计算性之界,只在效率层可能占优(肖尔算法对素数分解); 它动摇的是相似性原则,不是丘奇-图灵论题;
- 彭罗斯是唯一"抓到点子上"的反 AI 论证:必须推翻丘奇-图灵论题才行, 而他的量子脑假设中间隔着两个未兑现的跳跃;
- "超级智能"要么是更快的图灵机,要么预设了超计算——原书称其为伪概念; 谈"超"之前,先问越的是"能算"的界还是"快算"的界。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 归约链:人是机器→数字计算机 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:31(搜「心-身」) · text/14-ch10.txt:48(搜「归约」) · text/14-ch10.txt:50(搜「等价于」) |
| 冯诺伊曼:神经系统本质是数字的 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:34(搜「神经系统的本质」) · text/14-ch10.txt:40(搜「费曼」) |
| 图灵机三部件 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:27(搜「纸带」) · text/14-ch10.txt:56(搜「读写头」) · text/14-ch10.txt:55(搜「有限状态」) |
| 强大因为简单、哥德尔信服 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:59(搜「简单」) |
| 丘奇-图灵论题:观察不是定理 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:64(搜「Church-Turing thesis」) · text/14-ch10.txt:65(搜「观察」) · text/14-ch10.txt:95(搜「归纳」) |
| 装置互相模拟、更像物理定律 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:67(搜「互相模拟」) · text/14-ch10.txt:96(搜「物理定律」) |
| 丘奇命名图灵机、λ 排版事故 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:27(搜「图灵机」) · text/14-ch10.txt:84(搜「帽子」) · text/14-ch10.txt:88(搜「柯里」) |
| UTM 与存储程序、随机寻址 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:110(搜「universal Turing machine」) · text/14-ch10.txt:114(搜「软件」) · text/14-ch10.txt:119(搜「随机寻址」) |
| computer 指人类计算者 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:23(搜「人类计算者」) · text/14-ch10.txt:499(搜「布莱彻利」) |
| 王浩悖论、多项式小指数大 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:153(搜「王浩悖论」) · text/14-ch10.txt:157(搜「而指数是大的」) |
| 最坏与平均 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:159(搜「最坏情况」) · text/14-ch10.txt:162(搜「单纯形」) |
| TSP、NP、P、NP完全、P对NP | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:165(搜「旅行商」) · text/14-ch10.txt:168(搜「NP完全」) · text/14-ch10.txt:175(搜「是不是等于P」) · text/14-ch10.txt:177(搜「排第三」) |
| 证明比验证难、写书比读书难 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:180(搜「证明一个定理」) · text/14-ch10.txt:181(搜「写书比读书」) |
| 相似性原则 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:190(搜「相似性原则」) · text/14-ch10.txt:191(搜「多项式的」) · text/14-ch10.txt:213(搜「强丘奇-图灵论题」) · text/14-ch10.txt:215(搜「推翻」) |
| 复杂性更有哲学含义 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:216(搜「哲学含义」) |
| 超计算、oracle、永动机 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:218(搜「超计算」) · text/14-ch10.txt:229(搜「oracle」) · text/14-ch10.txt:239(搜「永动机」) |
| 作者的超计算判据 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:235(搜「复杂性层面」) · text/14-ch10.txt:236(搜「在复杂性层面 不服从相似性原则」) |
| BSS 模型 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:250(搜「BSS」) · text/14-ch10.txt:259(搜「单位时间」) · text/14-ch10.txt:268(搜「可判定」) · text/14-ch10.txt:273(搜「线性规划」) |
| 量子计算、RSA 数字、肖尔 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:291(搜「量子计算」) · text/14-ch10.txt:346(搜「2512」) · text/14-ch10.txt:349(搜「肖」) · text/14-ch10.txt:351(搜「15」) |
| 量子不越可计算性之界 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:356(搜「不能求解图灵机不可计算」) · text/14-ch10.txt:357(搜「相似性原则冲突」) |
| 马尔三层、瓦连特三层 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:382(搜「三层假设」) · text/14-ch10.txt:384(搜「相似性原则」) · text/14-ch10.txt:409(搜「超级普适性」) |
| 人就是图灵机 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:422(搜「人就是图灵机」) |
| 能行性与效率 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:424(搜「能行性」) |
| 多依奇:彭罗斯抓到点子上 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:370(搜「彭罗斯」) · text/14-ch10.txt:370(搜「点子上」) |
| 彭罗斯的两个跳跃 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:484( 搜「两个跳跃」) · text/14-ch10.txt:484(搜「跳跃」) |
| 超级智能是伪概念 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:487(搜「伪概念」) |
| 生命游戏、新数学 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:450(搜「康韦」) · text/14-ch10.txt:466(搜「新数学」) |
| 计算理论写进中学教科书(作者立场) | 第3版 前言 | text/02-ch03.txt:44(搜「中学教科书」) |
| 从业者没听过丘奇-图灵论题 | 第10章 人是机器吗?——人工智能的计算理论基础 | text/14-ch10.txt:399(搜「反省」) · 第14章第 175 段(text/18-ch14.txt:175,搜「甚至不知道」) |