上页我们看到一台精巧的'计算机器'凭空出现——但它为何被造出来？这要追溯到一场数学家追逐百年的梦想。

上页讲到图灵想回答"什么是可计算的"。他的绝妙思路是：与其争论什么是"思考"，不如直接造一台最简单的机器，看它能做到什么。这台机器就是图灵机。

从左到右读：纸带把符号交给读写头，符号与状态送进δ，δ决定写什么、换什么状态、头往哪移。

上一页我们用纸带和读写头搭出了图灵机的'实物模型'。但要做严谨的数学讨论，每个零件必须有一个精确的名字和取值范围——这就是七元组的意义。

上一页我们把图灵机装进七元组的盒子。现在打开盒子看内部：状态、字母表、空格符——这"三件套"如何决定机器的一举一动？转移函数又凭什么成为整个计算的灵魂？

从左到右读：左两个量是 δ 的输入（一对），右三个量是 δ 同一瞬间给出的输出。

上一页 δ 规定了「在状态 q 读到 x 该怎么办」——但光有规则还不够,我们还要能记录「这台机器当前算到哪了」。这一步的全部现场信息,就叫即时描述。

前页我们用「即时描述」刻画图灵机的瞬间状态。但同一时刻，写法却有两种风格——下划线放哪里、空白怎么处理，不统一就会看着像两种语言。

从左到右是计算方向。每框是即时描述，箭头『a→b,D』是δ一次触发：读到a写b，读头按D移动。

ID 在转移函数驱动下一步步变形，但哪一步是「起点」？哪些状态宣告「结束」？这一页把计算的起止钉死。

图灵机的一次计算循环：读符号、查δ、写覆盖、移动、判断停机。

上页我们看到 TM 一步步执行——但跑完之后，凭什么说机器'算'出了结果？这就要定义'接受'与'拒绝'。

具体图灵机设计案例（配状态图）

状态复用、调用子例程的思想

上一页我们用一条纸带、一个读写头的图灵机完成了回文判定。自然要问——如果给它多条纸带，会算得更多吗？

看图理解多带→单带的编码思路：分隔符分轨，标记符定头，单带TM循环扫描模拟各带。

我们已经看到，多带图灵机能模拟单带图灵机。但能不能让一台固定不变的机器，去模拟任意一台图灵机？关键在于「编码」——把机器本身也变成可处理的数据。

我们已经把图灵机形式化为精确的数学机器——那么自然会问：能否造一台万能机器，自动判定任意图灵机会不会停机？图灵在 1936 年给出震撼答案：不可能。

上一页我们碰到了图灵机的天花板：停机问题不可判定。顺着这个缺口，一个自然的问题浮出来——会不会是我们描述「计算」的工具太弱，而不是计算本身有极限？

• ✓七元组将算法从直觉变为可严格讨论的对象
• ✓即时描述是刻画计算过程的唯一规范手段
• ✓所有可计算问题都归约为状态转移序列
• ✓通用图灵机证明一台机器可模拟一切计算
• ✓停机问题划定了计算的不可逾越边界

图灵机能读写无限磁带，有限自动机只能存有限状态——这一区别决定了它们能解的问题天差地别。

先独自想一阵，再对照参考答案看自己想偏了没有。