第7章：审视各种简单的系统，看看它们如何像更复杂的机器一样执行同样的计算

[murphywuwu]

• [ ] 7.1 lambda演算
• [ ] 7.2 部分递归函数
• [ ] 7.3 SKI组合子演算
• [ ] 7.4 约塔
• [ ] 7.5 标签系统
• [ ] 7.6 循环标签系统
• [ ] 7.7 Conway的生命游戏
• [ ] 7.8 rule 110
• [ ] 7.9 Wolfram的2，3图灵机

[murphywuwu]

第6章表明，即使一种很小的编程也有足够的能力去做有用的工作。而第5章勾勒出了一台通用图灵机的设计，它可以读取描述另一台机器的编码，然后模拟其执行。 通用图灵机的存在是及其有意义的。尽管任何一台个体的图灵机都有一个硬编码的规则手册，但是通用图灵机证明了设计这样一个装置的可能性。这个装置可以通过从纸带读取指令来完成任何任务。这些指令实际是控制机器硬件运行的软件。

[murphywuwu]

lambda演算是一种可用的编程语言

使用lambda演算实现一台图灵机，然后使用这台模拟出来的机器运行lambda解释器。 相反的情况也是一样的，也就是说，图灵机也能模拟lambda演算程序，通过在纸带上存储一个lambda表达式的描述，并不断根据规约规则对其进行修改，一台图灵机可以作为lambda演算的解释器。