计算模型：从有限自动机到图灵机
有限自动机、下推自动机、图灵机构成能力递增的层级，分别对应正则、上下文无关、递归可枚举语言。本章给出直觉与例子，为第十卷的严格讨论做铺垫，并解释 Church–Turing 论题为何是”论题”而非定理。
- 正则表达式不能匹配括号配对，因为有限自动机没有栈
- 图灵机是所有现代计算机的能力上界（忽略资源）
- λ 演算与图灵机等价，是函数式语言的根
有限自动机、下推自动机、图灵机构成能力递增的层级，分别对应正则、上下文无关、递归可枚举语言。本章给出直觉与例子，为第十卷的严格讨论做铺垫，并解释 Church–Turing 论题为何是”论题”而非定理。