2. 图灵机：进阶专题¶
2.1. 构造更复杂的机器¶
显然，图灵机可以接受一个输入并修改它。 我们将看到这方面的例子如何带来强大的计算能力，即使目前看来它们似乎并没有那么强大。 为了快速了解它们的能力，考虑下面这台用于接受 \(L(a^nb^nc^n)\) 的相对简单的机器。 这一点很重要，因为这个语言事实上并不是上下文无关的。 这意味着这台简单的图灵机正在做某些任何 DFA、NFA 或 PDA 都做不到的事情！
2.2. 无限制文法和上下文相关文法¶
图灵机显然能比 PDA 接受更多的语言，因此也比上下文无关语言更多。 是否存在与之匹配的文法类呢？ 或者至少，一个或多个更强大的文法类？ 这里我们将简要介绍两类这样的文法。
无限制文法（Unrestricted Grammars） 允许形如 \(u \rightarrow v\) 的产生式， 其中 \(u\) 属于 \((V \cup T)^+\)，\(v\) 属于 \((V \cup T)^*\)。 换句话说，无限制文法允许在左侧和右侧出现变量与终结符的任意组合。 唯一的限制是 \(\lambda\) 不能作为规则的左侧。 （所以"无限制"这个说法并非字面意义上的正确，但已经很接近了！）
上下文相关文法（Context Sensitive Grammars） 的限制稍微多一些。 一个文法为 CSG，当且仅当所有产生式都具有 \(u \rightarrow v\) 的形式， 其中 \(u, v \in (V \cup T)^+\) 且 \(|u| \leq |v|\)。 因此，CSG 不能在推导过程中产生的任何句型（sentential form）中缩减东西的数量。 换句话说，推导过程中产生的某个东西可以改变形式（甚至终结符也可以被改变），但那些东西不能完全消失。
为了说明它们的能力，考虑下面的 CSG。
该文法生成语言 \(L = \{ a^nb^nc^n : n \geq 1\}\)。 这大概不是你轻易能看出来的，也不是一开始就容易想到的文法。 CSG 相当难以使用。 但请你自己尝试构造一个串的推导。 你会发现变量 A 和 B 被用来控制终结符 a、b、c 的生成，以确保它们保持平衡。
尽管 CSG 与无限制文法的能力之间存在一些细微的差别， 但我们可以简单地说，由某个无限制文法生成的语言集合， 与由某台图灵机识别的语言集合相同。 相比之下，由某个 CSG 生成的语言集合， 与由某台在允许使用的内存量上受到一定限制的图灵机识别的语言集合相同。
2.3. 简单算术……以及更多¶
之前我们提到，在图灵机中表示数字的一个有用方法是用一元记法（unary notation）。 换句话说，值 \(n\) 用 \(n\) 个标记来表示（我们将使用符号 1）。 我们展示过一台实现增量函数（increment）的简单机器： 从输入数字的开头开始向右移动，直到找到第一个空格，把它改成 '1'。
既然我们已经看到了复制（copy）和移位（shift）机器的实现， 就很容易明白如何实现一些简单的数学函数。 两个用一元记法表示的数相加，只需要移过第一个数，直到找到第一个空格后面的 '1'， 然后把下一个数向右移位（使它成为第一个数的一部分）。 这应该能让你理解为什么我们宁愿用一元记法而不是二进制或其他进制。 想象一下用图灵机实现二进制加法！ 这当然是可能的，但做起来会有点繁琐。 当然，最初的计算机开发者就不得不做类似的事情。
乘法稍微复杂一些。 同样，它也用两块 1 来表示。 要做乘法，我们首先把第二个操作数复制一份放到它的右边。 然后擦除第一个操作数的第一个标记。 然后重复把输出长度延长第二个操作数的长度。 然后把第一个操作数的长度减一。 再重复这个过程，直到第一个操作数被完全擦除。 然后擦除原始的第二个操作数，把读写头（head）移到输出的右边，并停机（halt）。
只要付出足够的努力，我们就能建立起一个完整的数学运算库。
2.4. 图灵论题与算法¶
你现在对图灵机能完成什么有了一些直觉。 图灵机可以作为语言的接受器（acceptor），也可以作为转换器（transducer）（意思是它可以把一个串转换为另一个串）。 我们还展示了一些简单的数学计算。 虽然用"图灵机代码"编写可能会很痛苦，但确实是可能的。 我们还看到了如何构建更复杂的功能。 至少在概念上，我们讨论了如何复用机器，使更高级功能的编程更容易。
这能走多远？ 原则上，可以像任何计算机一样远。 对于这一说法，我们在此不再给出进一步的证明或论证，只说明一点：计算机程序本质上建立在一些简单的原语上，如顺序、分支和循环。 其余的只是方便的语法。 这些结构都可以在图灵机上实现。
图灵论题（Turing's Thesis）： 任何能够通过机械方式完成的计算，都可以由某台图灵机执行。
依据这一点，我们得到了 算法（algorithm） 这一术语的一个有用的工作定义： 求解某个函数的算法，就是求解它的一个图灵机程序。 使用这个定义，我们可以形式化地讨论哪些问题（函数）有算法，哪些没有。
稍后我们将讨论一些可证明没有算法的函数。 为了方便起见，我们不会用图灵机的术语来阐述论证。 但这正是当初发展图灵机概念的初衷。 其中一个更令人惊讶的结论是：可以实现一台以某个图灵机的表示作为输入、并在一段输入串上模拟其执行过程的图灵机！
