Question

在第 3 章和第 4 章，我们研究了简单计算模型的能力。我们已经看到如何识别复杂性逐渐增加的字符串、如何匹配正则表达式，以及如何解析编程语言，而且都是使用不太复杂的基本机器完成的。

但我们也看到，这些机器——有限自动机和下推自动机——都有很严格的限制，这些限制影响了它们作为现实计算模型的使用。我们的小型系统还要多强大，才能摆脱这些限制并完成正常计算机的所有工作呢？它还要多复杂才能对RAM 或硬盘的行为以及合适的输出机制建模呢？怎么才能设计一台能实际运行程序而不总是执行某个硬编码任务的机器呢？

20 世纪30 年代，阿兰·图灵（Alan Turing）致力于从本质上解决这个问题。在那个年代，单词computer 意味着一个人，通常是一个女人，她手工重复着一系列繁重的数学性操作以执行长长的计算。图灵当时正在寻找一种理解和描述“人肉计算机”操作特征的方法，这样同样的工作就可以完全由机器执行。本章，我们将看到图灵关于设计最简单的“自动化机器”的思想，这一机器具有手工计算的全部能力和复杂性。