第8章：探讨计算本身的能力

[murphywuwu]

• [ ] 8.1 基本事实
  • [ ] 8.1.1 能执行算法的通用系统
  • [ ] 8.1.2 能够替代图灵机的程序
  • [ ] 8.1.3 代表即数据
  • [ ] 8.1.4 可以永远循环的通用系统
  • [ ] 8.1.5 能引用自身的程序
• [ ] 8.2 可判定性
• [ ] 8.3 停机问题
  • [ ] 8.3.1 构建停机检查器
  • [ ] 8.3.2 永远不会有结果
• [ ] 8.4 其他不可判定的问题
• [ ] 8.5 令人沮丧的暗示
• [ ] 8.6 发生上述情况的原因
• [ ] 8.7 处理不可计算性

[murphywuwu]

计算机的实际目的就是执行算法。算法是一个指令列表。

[murphywuwu]

程序有两种身份。除了把程序当作控制一个特定系统的指令之外，我们还把程序看成是纯数据：一个表达式树，一个原始字符串，或者甚至一个更大的树