第1节 计算模型
计算模型
计算机科学发端于许多对于选择性数学计算“模型”的研究，以及对这些模型所能够表示的计算类型的研究。
一个难以琢磨的目标是，我们要找到一个能够表示所有实际计算的“最终”模型...
•开关
•逻辑门
•组合逻辑
•存储器
•有限状态机
有限状态机的局限性
尽管有限状态机很有用并且非常灵活, 但依然存在它无法计算的许多问题。
例如：
符合语法规则的圆括号检查器:
给定任意一个带有左右圆括号的编码字符串，如果对称则输出为1，否则输出为0。
尽管描述起来很简单，很轻松。
但该设备是否与我们所枚举的有限状态机中的某一个等价呢???
否!问题在于: 依赖于不同的输入，我们需要任意多个状态。必须“计算”出未匹配的左括号。一个有限状态机只能弄清楚有限数量的未匹配的括号：对于每个有限状态机来说，我们可以找到一个它无法检查的字符串。
