6.22. 图灵机导论¶
6.22.1. 通用计算模型¶
在本模块中，我们寻求定义一个尽可能简单的通用计算模型。原因是我们希望能够理解计算可能性的极限，而这在一个对"计算机"的复杂定义下相当难做到。但是，我们也需要确信，无论我们选择哪个模型，它确实代表了"计算机"的所有基本能力。特别是，我们希望这个模型能够计算我们的"普通"计算机所能计算的任何函数。
"状态机"很容易理解。有若干种不同的状态机，能力各不相同。我们将讨论其中特别的一种，称为 图灵机。
如果你修形式语言课程，你将会了解若干种简单状态机类型，比如确定性及非确定性的 有限自动机，以及 下推自动机 （PDA）。这些机器都有一些相似之处。它们都接受一个输入字符串。它们都从左到右、一步一步地（每次一个字符）扫过字符串。它们在到达字符串末尾时停止，然后做一个简单的决定：如果机器处于最终状态，那么它接受该字符串（作为机器接受的字符串语言的一员），否则它拒绝该字符串。换句话说，它们是某种语言的 接受器。它们所能做的一切就是确定一个字符串是否是该语言的成员（当然，那是一个相当有用的能力），而"更强大"的机器可以接受或拒绝来自更"复杂"语言的字符串。
但当我们谈论"计算"时，我们通常期望的要多得多。比如，嗯，"计算"的能力，而不只是接受。 "计算"到底是什么意思？例如，我们希望能把算术表达式 "\(2 + 3\)" 作为输入，而不只是判断它在语法上是不是合法的算术语句。我们希望能够计算出答案：5。这意味着我们需要能够输出那个计算出的值。或者准确地说，我们通过取输入字符串 "\(2 + 3\)" 并用输出字符串 "5" 替换它来"计算"一个值。
以其最一般的形式，我们可以把计算机所做的一切看作接受某个字符串作为输入，然后提供某个字符串作为输出。当然，像键盘、鼠标和显示器这样的现代外围设备给了我们丰富的方式来表达输入字符串（也许作为按钮按压），以及丰富的方式来解释输出字符串（比如，作为图片）。但把一切计算抽象为把输入字符串转换为输出字符串，在想象上并不牵强，而且没有能力损失。
这种转换的概念比简单接受要强大得多。接受输入并产生输出的机器被称为 转换器。
在下一节中，我们将介绍一个简单的机器，称为 图灵机，它就是一个转换器。它只比其他状态机稍微复杂一点。考虑到这些差异有多重要，这些差异看起来可能小得惊人。最终，我们将看到，图灵机可以做任何计算（就其把一种字符串转换成另一种字符串的基本能力而言），即使是最先进的现代计算机也能做到。
第一个差异是记忆。简单的确定性（DFA）和非确定性（NFA）状态机除了知道它们的当前状态外没有记忆，因此不会受到达到该状态的历史的影响。相比之下，PDA 有一个栈。这在什么样的语言可被接受方面造成巨大差异： DFA 只能接受所谓的 正则语言，而（非确定性的）PDA 接受任何 上下文无关语言。
考虑这三种语言：
\(L_1 = \{wcw^R\}\)，其中 \(w \in \Sigma^*\)，\(\Sigma = \{a, b\}\)。
\(L_2 = \{ww^R\}\)，其中 \(w \in \Sigma^*\)，\(\Sigma = \{a, b\}\)。
\(L_3 = \{ww\}\)，其中 \(w \in \Sigma^*\)，\(\Sigma = \{a, b\}\)。
这些差异看起来相当小，但结果却相当不同。 \(L_1\) 是确定性上下文无关语言。 \(L_2\) 是非确定性上下文无关语言。 \(L_3\) 根本不是上下文无关语言。
\(L_3\) 与其他语言的差异似乎与用栈作为记忆的局限有关。当我们读取第一个 \(w\) 并把它装入栈时，我们没有办法深入到栈底看到第一个字母，以把它与第二个 \(w\) 的第一个字母比较。但如果我们考虑其他记忆模型呢？例如，队列就能很好地解决我们的问题。但那样的话，队列将无法处理 \(L_2\)。两个栈可以模拟一个队列（你能看出怎么做吗？），因此一台有两个栈的机器可以同时处理 \(L_1\) 和 \(L_2\)。也许我们应该研究一下两台栈机器能处理什么样的语言类？也许我们应该考虑其他记忆模型？
事实证明，这些想法中的任何一个都不如图灵机所用的简单记忆模型那样有效。
6.22.2. 图灵机¶
6.22.3. 解释图灵机¶
接下来我们将查看讨论图灵机格局及格局之间转换的概念的记法。我们将更详细地研究图灵机的停机、接受和计算约定。最后，我们将介绍在数字上进行真实计算的记法。
