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