9.1.1. 计算模型¶

到目前为止，我们已经看到了一些简单的机器类型，例如 DFA、NFA、PDA、正则表达式。我们也看到了相应的文法：正则文法、上下文无关文法等。这些机器之间存在一些差异。 DFA 是确定性的。 NFA 添加了非确定性，这只是意味着对于同一个输入字符，从一个状态可以有多种选择。 PDA 添加了存储栈的概念。

这些机器都有一些共同点。它们都接受一个输入字符串。它们都从左到右逐个字符地遍历字符串。当它们到达字符串末尾时停止，然后做出一个简单的决定：如果机器处于最终状态，则接受该字符串，否则拒绝该字符串。换句话说，它们是某种语言的 接受器。它们所能做的就是确定一个字符串是否属于该语言，而"更强大"的机器可以接受或拒绝来自更"复杂"语言的字符串。

但是当我们谈论"计算"时，我们通常期望的还有很多。比如，实际上"计算"的能力，而不仅仅是接受。 "计算"到底是什么意思？例如，我们希望能够接受算术表达式 "\(2 + 3\)" 作为输入，并计算输出值 5。这意味着我们需要能够输出计算得到的值 5。或者换一种说法，我们可以通过接受输入字符串 "\(2 + 3\)" 并将其替换为输出字符串 "5" 来"计算"一个值。

在最一般的形式中，我们可以将计算机所做的一切视为接受某个字符串作为输入，然后提供某个字符串作为输出。当然，像键盘、鼠标和计算机显示器这样的现代外围设备为我们提供了丰富的方式来表达输入字符串（可能作为按钮按下），以及丰富的方式来解释输出字符串（比如说，作为图像）。但将计算视为将输入字符串转换为输出字符串并不需要太多想象力。

这种转换的概念比简单的接受要强大得多。一个接受输入并提供输出的机器称为 转换器。

在下一节中，我们将介绍一个简单的机器，即 图灵机，它是一个转换器。它只比我们目前为止看到的机器稍微复杂一点，操作上也只有略微不同。但这些差异是显著的。最终，我们将看到图灵机可以执行任何即使是最复杂的现代计算机也能执行的计算。