图灵机、可计算性与停机问题
图灵机的定义与变体、Church–Turing 论题、通用图灵机、停机问题的对角线证明、Rice 定理。本章说明不可判定性的实际后果：没有程序能判断任意程序是否终止、是否有 bug。
- 对角线法是可计算性的核心证明技术
- Rice 定理：程序的任何非平凡语义性质都不可判定
- 不可判定不妨碍对特定实例给出答案
图灵机的定义与变体、Church–Turing 论题、通用图灵机、停机问题的对角线证明、Rice 定理。本章说明不可判定性的实际后果：没有程序能判断任意程序是否终止、是否有 bug。