尼克大师《计算与智能的第一性原理》第二讲出来了——什么是计算？为什么说图灵定义了计算？为何计算机科学以他的理论为基石？笔记如下。
为什么是图灵？一场关于“计算”的趣味溯源之旅
TL;DR
我们今天谈“计算”，离不开 图灵：他给出了最简约的机器模型（图灵机），却能执行任何“有效的过程/计算”。哥德尔告诉我们形式系统有极限，丘奇/克里尼提供了等价的函数/λ演算刻画，Post画出了颇像汇编的指令系统；现代还有忙碌海狸、量子计算、类比计算这些挑战边界的故事。核心精髓一句话：图灵机——简单到近乎简陋，却普适到令人敬畏。
1）图灵之前：群星闪耀的序幕
-
- 哥德尔（1931）：不完全性定理——再强大的形式系统也有真命题无法证明。
- 他用的是原始递归函数，但不够大。后来引入了一般递归才覆盖更多。
- Emil Post：天才又悲情。他设计的规则系统很像汇编+GOTO；提出的 Tag 系统 后来与 乔姆斯基层级对接。可惜因健康和际遇，多数成果未被重视。
- Alonzo Church：提出 λ 演算；克里尼证明它等价于递归函数。哥德尔却嫌它“不够原子化”。
出场的是图灵（1936）。
他把“人类拿纸笔计算”的动作抽象成一台极简机器：
-
- 一条纸带（无限）；
- 一个读写头（0/1）；
- 有限状态；
- 左/右移动。
就这四样。简单到骨子里，但却牢牢抓住了“计算”的本质。
2）丘奇–图灵论题（CTT）：不是定理，却成共识
-
- CTT：一切“有效可计算”的，都等价于图灵机。
- 它不是定理，而是一种科学信念，因为“有效”这个直觉无法形式化证明。
- 强版（ECT）：任何合理模型都能多项式模拟彼此。量子计算正在这里“挤牙缝”。
图灵定边界：什么能算。复杂性理论吵个不停：算得快不快。
3）巨大数字 vs 微小机器
-
- 高德纳的上箭头：↑是幂，↑↑是幂塔，↑↑↑是塔的塔……都还可计算。
- 阿克曼函数：不是原始递归，但可计算。证明“原始”≠全部。
- 忙碌海狸（Busy Beaver）：能定义，但不可计算，增长比任何可计算函数都快。
教训：你能“定义”很多怪兽，但机器可能抓不住。
4）Post、乔姆斯基与“语言即思维”
-
- 乔姆斯基文法层级：0 型 ≙ 图灵机，3 型 ≙ 有限自动机。
- Post 的系统，其实就是粗糙的 0 型。
- 从这里衍生出一个大胆推论：语言≈思维；既然语言有机对应机器类，或许思维≈计算。
图灵测试（1950）：把“智能”翻译成“能否在对话中骗过人类”。背后仍然是“机器是符号处理器”的预设。
5）量子、模拟与超计算的诱惑
-
- 量子计算：在计算能力上没超出图灵机，但可能在效率上更快（如分解大数）。这冲击的只是强版 CTT。
- 模拟/BSS 模型：在实数上算，数学优雅，物理却难落地。
- 彭罗斯：人类意识非算法，可能与量子重力有关——充满想象，但无实验支持。
- 李政道：或许世界本质上是离散的，“连续”只是近似。很契合图灵机那种“离散步骤”的宇宙观。
结论：有很多花样，但没有哪个能真正突破图灵机的“可计算性外延”。
6）人物轶事（冷知识版）
-
- 哥德尔 & 爱因斯坦：常在普林斯顿散步。爱因斯坦说，他去高研院最大的乐趣是“和哥德尔一起散步”。
- 图灵 19 岁手稿《Nature of Spirit》：因挚友去世而思考心灵与身体，预示他后来的机器智能设想。
- Post 的叹息：他写信说，若自己在 1921 年就发表，也许就该是他证明不完全性。
- 高德纳：除了 TeX，他还发明了“箭头记号”，专门用来描述“让计算器自爆的超大数”。
- 冯诺依曼：称图灵机的普适性“绝对且无可救药的普适”。然后把它工业化，造出了冯氏结构计算机。
7）为什么 AI 总绕回图灵？
-
- 工程：编译器、虚拟机、本质都是“一个形式模拟另一个形式”。
- 理论：P vs NP 判定什么能有效算；忙碌海狸提醒我们，有些题目再聪明也无解。
- 语言驱动的 AI：从早期语法分析到今天大模型，依然走在“语言—计算—智能”的桥上。
8）随身备忘单
-
- CTT：有效计算 = 图灵可计算。
- ECT：效率等价，多项式模拟；量子挑战。
- Busy Beaver：能定义，不能算。
-
- 乔姆斯基层级：语法 ↔ 自动机。
-
- BSS 模型：实数域计算，物理难行。
9）精髓，一口气说完
图灵的伟大，不是把计算复杂化，而是把它简化到能涵盖一切。
0/1、左/右、读/写——这些微不足道的动作，却让哲学的直觉变成了能物理实现的机器蓝图。自此：
-
- 数学能证明极限（哥德尔、不完全性、Busy Beaver）；
- 语言学能接上机器（乔姆斯基层级）；
- 工程能造出智能的雏形（计算机、AI）。
所以每当我们问“什么是智能”，答案常常就写在一条无限纸带上。
