1. 图灵机导论¶

1.1. 通用计算模型¶

到目前为止，我们已经看到几种简单的机器类型，如 DFA、NFA 和 PDA。我们还看到了相应的文法（grammar）：正则文法、上下文无关文法等等。我们已经研究了非确定性的概念。非确定性不会影响 DFA 的能力（NFA 接受的语言与 DFA 相同）。但非确定性确实会影响 PDA 的能力（非确定性的 PDA 比确定性的 PDA 识别更多的语言）。

这些机器都有一些相似之处。它们都接受一个输入串。它们都从左到右、每次一个字符地扫过整个串。它们到达串尾时停止，然后做出一个简单的决定：如果机器处于终态，则接受该串，否则拒绝该串。换句话说，它们是某种语言的接受器。它们所能做的全部事情就是判断一个串是否属于该语言（当然，这是一种相当有用的能力），而"更强大"的机器能够接受或拒绝来自更"复杂"语言的串。

但是，当我们谈论"计算（computation）"时，我们通常期望的要远远更多。比如，嗯，能够真正地"计算"，而不只是接受。 "计算"到底是什么意思？例如，我们希望把算术表达式 "\(2 + 3\)" 作为输入，做的远比判断它是否是一个语法上正确的算术语句要多。我们希望计算出答案：5。这意味着我们需要能够输出这个计算出的值。或者准确地说，我们"计算"一个值，是把输入串 "\(2 + 3\)" 替换为输出串 "5"。

在最一般的形式下，我们可以把计算机所做的一切都看作接受某个串作为输入，然后产生某个串作为输出。当然，像键盘、鼠标和显示器这样的现代外围设备给了我们丰富的方式来表达输入串（比如通过按键），以及丰富的方式来解释输出串（比如作为图片）。但是，把一切计算抽象为把输入串转换为输出串，并不需要多么丰富的想象力，而且不会损失任何能力。

这种转换的概念远比简单的接受强大。接受输入并提供输出的机器被称为转换器。

在下一节中，我们将介绍一种简单的机器，称为图灵机，它就是一个转换器。它只比我们已经见过的机器稍微复杂一点，在运行方式上也只稍微有一点不同。考虑到这些差异是多么重要，它们看起来可能小得惊人。最终，我们将看到，图灵机能够完成任何计算（在其把一种串转换为另一种串的基本能力范围内），即使是功能最强大的现代计算机所能完成的任何计算也不例外。

第一个差异是内存（memory）。 DFA（和 NFA）除了将它们带到当前状态的执行过程之外没有任何内存。 PDA 有一个栈。这给可接受的语言带来了巨大差异： DFA 只能接受正则语言（regular language），而（非确定性的）PDA 能接受任何 CFL。

考虑以下三种语言：

\(L_1 = \{wcw^R\}\) for \(w\) in \(\Sigma^*, \Sigma = \{a, b\}\) .
\(L_2 = \{ww^R\}\) for \(w\) in \(\Sigma^*, \Sigma = \{a, b\}\) .
\(L_1 = \{ww\}\) for \(w\) in \(\Sigma^*, \Sigma = \{a, b\}\) .

这些差异看起来相当小，但结果却截然不同。 \(L_1\) 是确定性的 CFL。 \(L_2\) 是非确定性的 CFL。 \(L_3\) 根本不是 CFL。

\(L_3\) 与其他语言之间的差异似乎与栈的局限有关。当我们读取第一个 \(w\) 并将其装入栈时，无法方便地深入到栈底去查看第一个字母，以便与第二个 \(w\) 的第一个字母比较。但如果我们考虑其他内存模型呢？例如，队列（queue）就能很好地解决我们的问题。但那样的话，队列无法处理 \(L_2\)。两个栈可以模拟一个队列（你能看出怎么做吗？），因此一台有两个栈的机器可以同时处理 \(L_1\) 和 \(L_2\)。也许我们应该研究一台双栈机器能够处理什么样的语言类？也许我们应该考虑其他内存模型？

事实证明，这些方案没有一种像图灵机所使用的简单内存模型那样有效。