从沙子到车辙（1.3）：图灵的答案

1.3 图灵的答案那个跑步穿过剑桥的人1935 年剑桥大学国王学院。一个 23 岁的研究生躺在草地上望着天空想着一件事什么是计算他叫艾伦·图灵Alan Turing。这个年轻人身上有很多标签天才、怪人、马拉松运动员。在图灵的传记里你不会看到社交达人这个标签。他有时会戴着防毒面具在办公室工作——不是为了防止病毒而是为了防止花粉过敏。他会把自己的茶杯用链条锁在暖气片上以防别人偷用。他说话结巴但不妨碍他用极快的速度思考数学问题。他跑步极快——1948 年伦敦奥运会马拉松选拔赛上他跑出了 2 小时 46 分的成绩只比英国代表队最后一名的成绩慢 11 分钟。他在训练时有时会从剑桥一路跑到伦敦——约 80 公里——就为了赶上一个会议。但图灵最惊人的跑动不是身体上的——是精神上的。当时数学界刚刚被哥德尔震撼我们知道有些命题不可证。但如何判断一个命题是可证的还是不可证的希尔伯特的第三个问题——判定问题Entscheidungsproblem——问的是是否存在一套机械步骤能自动判定任意数学命题是否为真要回答这个问题你首先要定义什么叫机械步骤。“一步一步算”——这句话说了等于没说。你得给出一个精确的数学模型。不能含糊。不能用自然语言。不能用直观上显然。图灵躺在草地上脑子里浮现出一个工人——坐在桌子前面前是一条分成一个个方格的纸带手边是一张写了规则的表。他低头看当前格子的符号看一眼规则表然后在纸带上改写符号、把纸带向左或向右移一格、抬头看新格子的符号——如此循环。没有灵感没有直觉没有创造性思维。每一步都严格按照表上的规则做。这就是图灵机的雏形。一条纸带一个状态表图灵机的设计极度简约。三个组件纸带一条无限长的带子分成一个个方格每个方格可以写一个符号比如 0 或 1也可以是空白_。纸带可以向左或向右移动一格。无限长是一个理论假设——在物理世界中纸带当然是有长度的。但图灵问的是如果资源无限计算的边界在哪里先问清楚终极边界再看物理约束把它缩小到哪里。读写头当前正对着纸带的某一格可以读取这一格的符号也可以擦掉、写入一个新符号。然后根据规则决定把纸带向左移一格L或向右移一格R。有限状态控制器机器内部有一组有限数量的状态——S1, S2, S3, … HALT。在每个状态下根据读取到的符号机器会做三件事写入一个新符号可能和原来一样、移动纸带、切换到另一个状态或停机。所有可能的行为都可以写在一张状态转移表里当前状态 | 读取符号 | 写入符号 | 移动方向 | 下一状态 S1 | 0 | 1 | R | S2 S1 | 1 | 0 | L | S3 S2 | _ | _ | N | HALT这张表就是程序。一条纸带、一个读写头、一张状态转移表——这就是整台机器的全部零件。没有 RAM、没有 ALU、没有缓存、没有流水线、没有指令集。只有这三样。看起来简单得可笑是。但图灵的惊人结论是如果一个问题有机械解法就存在一台图灵机可以做到。图灵机实操计算两个数的加法让我们把这台机器跑起来直观感受一下它到底怎么计算。假设纸带上存着两个数——用一串连续的 1 来表示。比如3就是 “111”“2” 就是 “11”。两个数之间用一个空格_隔开。初始状态纸带看起来像这样... _ _ 1 1 1 _ 1 1 _ _ ... ^ 读写头我们要让图灵机把这两个数合并成一个——即 111_11 变成 11111实现 3 2 5。状态转移表如下状态 | 读取 | 写入 | 移动 | 下一状态 | 说明 S1 | 1 | 1 | R | S1 | 向右扫遇到 1 保持 1 S1 | _ | 1 | R | S2 | 遇到空格填上 1 S2 | 1 | 1 | R | S2 | 继续向右扫过第二个数 S2 | _ | _ | L | S3 | 遇到第二个空格回退一格 S3 | 1 | _ | N | HALT | 擦掉最后一个冗余的 1停机执行过程纸带初始111_11读写头在最左边第1步: S1, 读 1 → 写 1, 右移, 仍是 S1 纸带: 111_11 第2步: S1, 读 1 → 写 1, 右移, 仍是 S1 纸带: 111_11 第3步: S1, 读 1 → 写 1, 右移, 仍是 S1 纸带: 111_11 第4步: S1, 读 _ → 写 1, 右移, 进入 S2 纸带: 1111_11 (空格变成 1) 第5步: S2, 读 1 → 写 1, 右移, 仍是 S2 纸带: 1111_11 第6步: S2, 读 1 → 写 1, 右移, 仍是 S2 纸带: 1111_11 第7步: S2, 读 _ → 写 _, 左移, 进入 S3 纸带: 1111_11 (碰到尾端空白) 第8步: S3, 读 1 → 写 _, 不动, HALT 纸带: 1111_1_最后纸带上是11111前面还有 4 个 1 加上位于原来空格空白位置后面那个未被覆盖的 1HALT 前我们把最后一个多余 1 也擦了——实际执行需要略微调整。上面的例子重点在于感受这个过程每一步都在做同一件事——“读符号 → 写符号 → 移纸带 → 换状态”。六个步骤计算完成。现在说句实话刚才那个加法用汇编写是ADD R0, R0, R1——一条指令一个时钟周期。但图灵机用了 8 步。图灵机的单个步骤比 CPU 指令原始得多——它是“计算的原子”。你把它看成计算的夸克——不是因为它快而是因为它不可再分。任何更复杂的计算操作——ADD、MUL、条件跳转、函数调用——都可以分解成这种原子操作。用代码模拟图灵机让我们更进一步——用 Python 写一个通用图灵机解释器。你只需要定义纸带、状态转移表、初始状态它就能模拟任何图灵机的执行# 通用图灵机解释器defturing_machine(tape,transition_table,initial_state,initial_pos0):stateinitial_state posinitial_pos steps0max_steps1000# 防止真·无限循环whilestate!HALTandstepsmax_steps:# 读取当前位置符号symboltape[pos]ifposlen(tape)else_# 查表在当前状态、当前符号下转移到哪个新状态key(state,symbol)ifkeynotintransition_table:print(f未定义转移: state{state}, symbol{symbol})breaknew_symbol,direction,new_statetransition_table[key]# 写入ifposlen(tape):tape[pos]new_symbolelse:tape.append(new_symbol)# 移动ifdirectionR:pos1elifdirectionL:posmax(0,pos-1)# direction N 不动# 切换状态statenew_state steps1returntape,state,steps# 例二进制非运算把 1100 变成 0011tape[1,1,0,0]table{(S1,1):(0,R,S1),(S1,0):(1,R,S1),(S1,_):(_,N,HALT),}result,final_state,stepsturing_machine(tape,table,S1)print(f结果:{.join(result)})# 结果: 0011这个解释器只有 30 行但它能执行任何图灵机可计算的问题。你给它不同的transition_table它就做不同的计算。解释器 固定的硬件transition_table 可替换的软件。看起来像什么像操作系统加载不同的 ELF 文件执行不同的任务。像 CPU 取不同的机器码做不同的操作。这个 30 行的 Python 脚本和你的 S32K144 的 ARM Cortex-M4F 核心是同一种东西通用图灵机的物理化身。通用图灵机一套硬件统治一切图灵的第一篇论文不只定义了普通图灵机——他更进一步定义了一类特殊的机器通用图灵机Universal Turing MachineUTM。普通图灵机的纸带上只有数据。通用图灵机的纸带上同时有数据和程序。程序就是一个目标图灵机的状态转移表的编码。通用图灵机读取纸带上的程序模拟那台目标图灵机的全部行为。这意味着什么一台固定的机器——它的状态转移表是固定的只需要几十个状态——可以执行任何计算。你不需要为加法造一台加法机、为乘法造一台乘法机、为排序造一台排序机。你只需要把加法的状态表的编码放到纸带上通用图灵机读它、模拟它——然后你的机器就变成了加法机。你再换一段纸带、放上乘法的状态表——同一台机器又变成了乘法机。程序和数据共处纸带之上。你换纸带上的内容就换了整个世界。这就是软件概念的真正诞生。你再回头看你的 ECU。同一颗 NXP S32K144烧录不同的固件Firmware它就扮演完全不同的角色烧录网关固件 → CAN 报文路由引擎。烧录 BCM 固件 → 车身控制模块灯光、门锁、雨刷。烧录 ABS 固件 → 防抱死制动控制器。同一套 ARM Cortex-M4F 物理核心同一套 CAN 外设同一套 SRAM 地址空间。区别只在于 Flash 里烧的那几十 KB 机器码的内容。就像图灵的纸带——你换一张纸带机器就换一个灵魂。这就是通用计算的本质硬件是身体软件是灵魂。换灵魂不换身体。丘奇-图灵论题一个未证明但确凿的共识图灵在剑桥推导图灵机模型的同时大洋彼岸的普林斯顿另一位逻辑学家阿隆佐·丘奇Alonzo Church也在用另一种方式定义计算。丘奇发明了λ 演算Lambda Calculus。它不像图灵机那样物理化纸带 读写头而是极度数学化——一切计算都是函数的定义和应用。λ 演算只有三条规则变量x 是一个 λ 项。抽象λx.M是一个 λ 项——定义一个参数为 x、函数体为 M 的函数。应用M N是一个 λ 项——把函数 M 应用到参数 N 上。就这么简单。没有纸带没有状态表没有读写头。只有三个规则——但它也是图灵完备的。任何图灵机可以计算的函数λ 演算也可以计算。丘奇的 λ 演算虽然看起来不接地气但它直接影响了现代编程语言。你写的 JavaScript(x) x 1Python 的lambda x: x 1C 的[](int x) { return x 1; }Haskell 的\x - x 1——这些全部是丘奇 λ 演算的直接后代。λ 的箭头从来没有消失——它只是从数学论文飞进了编程编辑器的语法高亮。图灵在 1936-1938 年间去普林斯顿做访问学者在阿隆佐·丘奇Alonzo Church指导下。丘奇成了他的导师。图灵证明了图灵机模型和 λ 演算模型计算能力等价。一个函数是图灵可计算的当且仅当它是 λ 可定义的。这个等价性引出了一个更深刻的命题——丘奇-图灵论题任何在物理上可计算的过程都可以用图灵机来模拟。论题没有被数学证明——因为它连接了物理世界和数学世界而这类跨越性的命题无法用纯数学手段确立。但在近一个世纪里没有一个人提出过反例。量子计算、DNA 计算、神经形态计算——它们可以算得更快但计算的范围都没有超出图灵机的边界。丘奇-图灵论题不是一个定理——它是人类文明在近一个世纪的沉默共识。你踩过的每一行代码、你用过的每一个 CPU 指令、你编译过的每一个 ELF 文件——都在以物理载体的形式对这个论题投赞成票。图灵在布莱切利园理论与世界的碰撞图灵不只是个理论家。二战爆发后他被召入英国政府密码学校派往布莱切利园Bletchley Park——英国二战密码破译的中心。德军用一台叫恩尼格玛Enigma的机电密码机加密他们的军事通信。恩尼格玛有三个转轮、一个插线板每按一个键内部电流路径都会变化使得同一个字母在两次按键中会被加密成不同的字母。理论上可能的密钥空间大约是 10²³——这个量级人工暴力破解是不可能的。图灵在 1940 年设计了一台叫“炸弹”Bombe的电机设备。它不是通用计算机——它是一台专门破解恩尼格玛密码的机器——但它用继电器逻辑实现了自动搜索可能密钥的算法。Bombe 利用了图灵观察到的一个关键弱点德军每天早上都会发送一份包含WETTER天气这个词的加密电报——已知明文攻击。Bombe 模拟多台恩尼格玛机并行运转检查每一种可能的转轮设置筛出那些能把可能的明文和截获的密文对应起来的设置。到了战争末期布莱切利园平均每天破解 3000 条敌方消息。历史学家估计图灵的 Bombe 和后续破解工作使二战至少缩短了 2 年挽救了约 1400 万人的生命。但图灵在世时这一切都是国家机密——他不能说。他的母亲只知道他在城里为政府做一点文书工作。而图灵的同事汤米·弗劳尔斯Tommy Flowers在 1944 年造出了科洛萨斯Colossus——世界上第一台可编程电子计算机。科洛萨斯用 2400 个真空管搭建而成专门破解德军最高级别的洛伦兹密码。Colossus 不是通用图灵机——它的程序是预先用插头配线板设定的——但它证明了电子逻辑电路可以高速执行复杂算法。每秒处理 5000 个字符。战后英国人把所有 Colossus 机器拆成零件、烧掉图纸——最高机密。参与项目的人被勒令永远不许提及。直到 1970 年代Colossus 的存在才被公开。图灵和弗劳尔斯在布莱切利园的工作可能是人类历史上最具影响力的秘密计算项目。纸带会发霉一个半导体工程师的插曲图灵机的纸带是理想纸带——无限长、不磨损、不褪色、不发霉。但现实世界的存储介质不是这样的。在半导体制造领域SRAM 是芯片良率最敏感的部位。SRAM 的密度最高——一颗标称 512KB 的 Flash MCU 上SRAM cell 可能占用 70% 的晶体管数。在线电子束检测的时候可以看到某些 SRAM bit 的阈值电压存在轻微偏移——偏到一定程度某个操作电压点就翻转了。这是Vt mismatch——深亚微米工艺中掺杂原子的随机涨落导致的6T SRAM 单元的交叉耦合反相器对里的晶体管不够匹配稳态点就偏向了一边。读/写噪声一干扰值就变了。图灵的纸带是完美的。你的硅纸带不是。在太空环境中高能粒子宇宙射线穿过芯片直接把某个 SRAM 单元撞翻——这叫SEUSingle Event Upset。在地面上alpha 粒子从封装树脂里的微量铀/钍同位素衰变出来也一样能撞翻 SRAM。汽车电子的 ISO 26262 要求 ASIL D 级别的 ECU 必须实现 ECCError Correcting Code或 lockstep 双核比对——本质上就是给图灵机的纸带加了一层纠错机制。理想的计算模型忽略了物理世界的不完美——而工程师的一生都是在补偿这些不完美。你写的 C 代码就是一张状态转移表让我们从布莱切利园和产线回到你的工位。你写了一行嵌入式 Cintsum0;for(inti0;i10;i){sumi;}这段代码的图灵机等价是什么纸带 内存RAM Flash。纸带上的符号 内存地址上的值。读写头 CPU 的 Load/Store 单元。ldr是读str是写。状态表 指令序列。当前状态 程序计数器PC指向的地址。下一条指令 PC 4ARM 上。编译器把它翻译成 ARM 汇编mov r0, #0 ; sum 0 mov r1, #0 ; i 0 loop: cmp r1, #10 ; 比较 i 和 10 bge end ; 如果 i 10跳出 add r0, r0, r1 ; sum i add r1, r1, #1 ; i b loop ; 回到循环开头 end:你看这就是一张状态转移表——只是用汇编助记符写了出来。mov、cmp、add、b——这四个助记符是状态转移表的高速语法。编译器做的事就是把你的 C 代码——if、for、while——翻译成图灵机的状态转移表。没有例外。你写过的每一行代码、每一个 bug、每一个性能优化——都是在这张有限状态表上做的微调。简约的震撼图灵机最让人震撼的不是它的能力——而是它的简约。一个无限长的纸带。一个有限的状态表。没了。复杂的事物可以还原到简单的规则。这是一个极具哲学和美感的洞见。你开的那辆车上可能有 100 多个 ECU上千万行代码。CAN 总线上每秒跑着几千帧报文。MOST 总线上传着高保真音频。以太网上跑着 DoIP 诊断请求。时间同步协议在幕后调整着各节点的时钟。如果拆到最底层——都是纸带、读写头、状态表。本质不是复杂的。复杂是本质的展开。造车也一样。一辆车有上万个零件。材质有钢、铝、碳纤维、橡胶、陶瓷。工艺有冲压、焊接、涂装、总装。供应商遍布全球。但如果拆到最底层——都是原子排列。物理定律。工程劳动。人类用原子造出了钢铁用钢铁造出了车身用硅造出了芯片用芯片控制了车身。一层一层的递进不是魔法是几百年来科学发现和工程迭代的累积。你站在纸带上的那一刻已经站在了人类计算文明的起点。本篇小结今天我们做了一件事理解了图灵机为什么是人类思想史上最简约的发明之一。关键结论图灵机的三要素——纸带、读写头、状态表——定义了一切机械计算的边界如果一个问题有算法解就存在一台图灵机可以做到。通用图灵机宣告了软件的诞生同一套硬件换一张纸带就是一台全新的机器——你换固件ECU就换了灵魂。你写的每一行C代码底层都是一张状态转移表编译器把if、for、while翻译成图灵机的原子操作——没有任何例外。下一节我们问一个更尖锐的问题图灵机有什么算不了的【下集预告】图灵机这么强大——那它有什么算不了的东西吗答案是有。而且这个发现会直接关联到你修复不了的那个偶发 bug。你的老板让你写一个程序——“读入任意程序的源代码判断它会不会跑飞”。你告诉他这不只是难——它数学上就做不到。不管你多聪明不管你写多长的代码不管你编译多少次——有些问题计算机永远解决不了。这就是计算的边界。下一章我们走进那道边界看它是什么形状——以及聪明的工程师是怎么在边界上搭桥的。本文内容摘自本人的开源书《从沙子到车辙 - 一个工程师的理解》 在线阅读/下载from-sand-to-rutsgitclone https://github.com/Lularible/from-sand-to-ruts⭐ 如果对您有帮助欢迎 Star 支持也欢迎通过 GitHub Issues 交流讨论。