图灵机是如何被逼出来的（历史）
这台机器不是被发明出来的，而是从"人类遵循规则时到底在做什么"这件事里提炼出来的。这段历史说明了为什么它的每一个特征都非有不可。
1. 动机：希尔伯特的判定问题（Entscheidungsproblem，1928）
希尔伯特要求给出一个确定的方法，对任意一阶逻辑命题，判定它是否可证。要回答这个问题——尤其是要证明不存在这样的方法——就必须先给"算法/可有效计算"下一个数学定义。在 1936 年之前，"算法"只是一个直觉概念，并没有形式定义。这个空白就是动机所在。
2. 三种独立的形式化（1934–36）
- 哥德尔–埃尔布朗（1934）：一般递归函数 ——由方程组定义；等于原始递归加上 Kleene 的
μ-算子（无界搜索，即"满足……的最小n"），正是这个算子让它逃出了那个总会停机的原始递归世界。 - 丘奇（1936）：λ-演算 ——"可有效计算"⟺"λ-可定义"；被用来证明判定问题无解。
- 图灵（1936）：图灵机 ——落在同一个类里，却是通过分析计算本身得到的。
3. 图灵的分析（机器为什么长这个样子）
图灵问的是：一个人类计算者——一个按固定规则做计算的人——实际上在做什么？人的每一个真实局限，都变成了机器的一个特性：
从人类计算者推导出机器
- 纸上的符号 → 理想化为一条一维的、划分成方格的纸带。
- 注意力有限 → 只有一个有限字母表，每次只读一个方格。
- 下一步动作取决于看到的符号，以及一个必须是有限的"心智状态"（可区分的心智状态只有有限多个）。
- 每一步：由
(状态, 符号)→ 写/擦，向左或向右移动一格，改变状态。
这就是一个机械步骤所能是的全部——这正是为什么最终得到的机器能够令人信服地充当算法的定义。哥德尔本来既不认可 λ-演算，也不认可自己提出的递归方程，但接受了图灵的分析是决定性的。
4. 丘奇-图灵论题
图灵和克莱尼（Kleene）证明了 λ-可定义 = 一般递归 = 图灵可计算——三个互不相关的出发点，落在了同一个类里。克莱尼建立了递归论（μ-递归、范式、s-m-n 定理、递归/不动点定理），并且提出了"丘奇论题"这个说法。
丘奇-图灵论题"可有效计算" = "图灵可计算"。这是一个论题，不是一个定理——它把一个非形式化的概念和一个形式化的概念等同起来；支持它的证据，是所有独立的形式化最终都坍缩进了同一个类。
5. 回报：停机问题，回到希尔伯特
通用机让一台机器可以谈论机器。对它做对角化，就得到halting-problem——没有一台机器能判定任意 (M,x) 是否停机。再把停机问题归约到可证性，就回答了希尔伯特的问题：判定问题无解——这是第一个自然出现的不可判定问题，也是recursion-is-a-phase-transition所说的图灵/哥德尔那道门槛。