模拟

图灵机比我们研究过的其他机器更强大，能够执行各种各样的任务。图灵机程序的一个更有用的技巧是模拟另一台机器的操作。

在下面的示例中，我将演示如何构造一个能够忠实地复制PDA行为的图灵机程序。我在这个例子中使用的技术是相当通用的，并且可以赢博体育于我们需要构建图灵机来模拟另一台机器的行为的其他情况。

为了模拟PDA的输入和堆栈，图灵机将使用一种特殊配置的磁带。磁带将记录输入的当前状态和堆栈的当前状态。

假设我们想要向PDA提供一个特定的输入字符串s。在图灵机模拟中，我们将从磁带上的输入字符串s开始。当机器运行时，图灵机会想要跟踪PDA读取输入数据的进度。一种自然的方法是使用标记系统。每走一步，图灵机都会在PDA要读取的下一个字符上做一个标记。为了记录堆栈的状态，图灵机会在输入后放置一个特殊的分隔符#，然后将堆栈的内容放在#之后。出现在#后面的字符代表堆栈的底部，而磁带上的最后一个字符代表堆栈的顶部。

下图显示了图灵机磁带的典型配置。

这对应于图灵机模拟的PDA即将读取其输入的第三个字符的情况（注意0上的点-这是机器在输入中标记当前位置的方式），而堆栈当前包含符号1和1。

接下来，我们将构建图灵机的控制。以下是我们将如何做到这一点的一些指导方针。

PDA中的每个状态在图灵机中都有对应的状态。图灵机将在这些状态之上添加额外的状态来运行模拟。
在与PDA的开始状态相对应的状态之前，我们将添加一些初始化的附加状态，包括标记输入的第一个字符和在磁带上添加#字符。
对于PDA中的每个转换，我们将向图灵机添加转换和附加状态，以连接PDA转换所连接的两个状态。
我们将添加额外的状态和转换，使我们能够忠实地模拟PDA中最终状态的行为。

下面是一个示例，演示如何将PDA转换映射到图灵机的片段。

这是一个典型的PDA转换

模拟图灵机将具有标记为a和b的控制状态，它们对应于这两个PDA状态。连接状态a到b的图灵机将有一个复制原始转换行为的片段。当且仅当当前PDA配置允许在PDA中进行相应的转换时，图灵机才有可能在仿真中从a到b。

这是图灵机片段对应于这个PDA转换。

这就是这个片段的作用。

该片段假设当图灵机处于状态a时，磁带头将位于磁带上的虚线字符上方，准备读取模拟输入中的下一个字符。
片段首先确认磁带头下面的符号是带点的1。原始PDA只有在输入中的下一个字符为1时才能从状态a切换到状态b。
然后，片段向右移动到堆栈顶部对应的单元格，并确认那里有一个0。

如果堆栈顶部没有0，则片段倒回到带点的1并返回到状态a：转换尝试失败。

如果在堆栈的顶部有一个0，片段将删除它并倒回到带点的1。
该片段将点1替换为普通的1，将字符点到右侧，并将磁带头放置在新点字符上。如果原虚线1之后的下一个字符是#，则片段将保持该字符不变，并以#上的磁带头结束。

一个更完整的模拟示例

我们使用图灵机的一个非常常见的技巧是展示它如何模拟其他机器。这也适用于反向：在某些情况下，我们可能想要展示一些机器可以模拟图灵机。

在下一个例子中，我们将展示一个有两个堆栈的机器可以模拟图灵机。

演示这种模拟如何工作的第一步是解释我们如何使用两个堆栈来模拟图灵机中磁带的状态。下面的图片显示了它是如何工作的。

左边的堆栈保存了出现在磁带上的赢博体育符号，这些符号要么在磁带头下面，要么在磁带头左边。磁带上的第一个符号出现在堆栈的底部附近，磁带头下面的符号出现在左侧堆栈的顶部。除了这些符号之外，左边堆栈的底部还包含一个标记符号$。这标志着磁带的左端。右边的堆栈保存出现在磁带头右边的磁带符号。紧靠磁带头右边的符号出现在右堆栈的顶部，磁带上的第一个空白出现在第二个磁带的底部。

首先要注意的是处理输入。图灵机被期望从它在纸带上的输入开始，纸带头在输入的第一个符号上，而PDA读取它的输入。我们可以通过在图灵机的开始状态之前插入一个子片段来处理这个问题，该子片段将$压入第一个堆栈，将空白压入第二个堆栈，然后读取输入并将读取的每个符号压入第一个堆栈。然后必须紧接着第二个子片段，它将符号从左堆栈传递到右堆栈，直到我们在左侧看到$。然后我们将一个符号从第二个堆栈的顶部移动到第一个堆栈的顶部。我们还需要这个片段在输入为空的特殊情况下做正确的事情。

这个预启动片段是机器中唯一读取输入的部分。在此之后显示的赢博体育用于双堆栈机器的指令都将简单地忽略输入。

接下来，我们将展示如何模拟一个典型的图灵机指令。图灵机指令有三个部分：读符号、写符号和移动磁带头。为了检查一个特定的符号是否出现在磁带头下，模拟只需尝试从第一堆栈的顶部弹出该符号。如果该符号没有出现在第一个堆栈的顶部，则弹出尝试失败，我们什么也不做。这与图灵机指令在所需符号没有出现在磁带头下的情况下所做的操作相匹配。要写入一个符号，只需将该符号压入第一个堆栈的顶部。为了模拟向左移动，我们从第一个堆栈中取出一个符号，并将该符号压入第二个堆栈。为了模拟向右移动，我们从第二个堆栈中取出一个符号并将其推入第一个堆栈。

最后，我们必须确保我们正在妥善处理特殊情况。有两种特殊情况需要考虑。

第一个特殊情况是试图将磁带头从磁带的左端移到左边。为了处理这个问题，我们在每个片段的末尾添加了一个额外的过渡，以模拟图灵机指令。这个片段检查第一个堆栈顶部的符号是否为$标记。在模拟中达到这种状态的唯一方法是从堆栈的左端向左移动，所以我们只需要撤销之前的向左移动。我们通过将符号从第二堆栈的顶部弹出并将其推回到第一堆栈的顶部来实现这一点。这有效地取消了之前的向左移动。

第二个特殊情况是移动到空白位置。为了处理这个问题，我们向片段中处理向右移动的部分添加了一些额外的逻辑。当我们从第二个堆栈中取出符号时，我们检查刚刚取出的符号是否为空白。如果是，则插入一条指令，将另一个空白压入第二个堆栈的顶部。之后，我们将原始空白压入第一个堆栈的顶部。

这里有几个完整的模拟指令的例子。第一个例子是一个以向左移动为特征的指令，包括检查是否试图向左移动过磁带的左端。如果最初的图灵机指令看起来像

模拟碎片看起来像

第二个例子是一个向右移动的指令，包括检查是否向右移动到空白。

模拟片段为

只有最后一种特殊情况需要考虑，即输入为空的情况。大多数图灵机都有一个特殊的情况指令来处理这种情况，立即转换到接受状态或拒绝状态。对于这种情况，我们的模拟是否需要进一步的特殊处理，或者现有的措施是否足以自动处理这种情况，我将留给您作为练习。

多磁带图灵机

在本文的3.2节中，作者讨论了基本图灵机的几个重要变体。第一种是多磁带图灵机，它有几个磁带，每个磁带都有自己独立的磁带头。多磁带机中的典型转换指定每个磁带头下面应该出现什么符号，在当前单元中写入什么符号，以及如何移动每个磁带头。除了通常的L和R移动之外，多磁带图灵机还允许“停留”命令S。

这张图显示了典型的多磁带机配置以及典型的转换。

在某些情况下，我们可能希望对磁带的一个子集做一些事情，而保留剩余的磁带不变。我们可以通过引入通配符*来更容易地指定这些类型的转换，*可以匹配磁带上的任何符号，并对我们希望保持不变的任何磁带使用转换*→S。

就像我们可以用单带图灵机来模拟PDA一样，我们也可以用单带图灵机来模拟多带图灵机。我们简单地用#字符将不同磁带的内容连接到一个磁带上，以分隔各个磁带的内容，并使用标记系统来指示磁带头在不同磁带中的位置。它看起来像这样：

正如我们在PDA示例中所做的那样，我们将创建一个具有与原始多磁带机相同状态的新控件。我们将用做以下事情的片段替换原始机器中的赢博体育转换：

从左到右扫描磁带，确认每个子段上的点对字符是正确的。
第二次扫描磁带，更换并移动单个磁带磁头。
倒回到单磁带的开头。

在这种情况下，我们必须解决的另一个复杂问题是，当我们向特定磁带写入更多字符时，单个段可能会增长。在这种情况下，碎片还必须配备移动字符组到右边，为我们想要写的字符创造空间。这是一个痛苦的过程，但可以做到。

展望未来，我们将可以自由地在一个解决方案中使用多个磁带，因为我们现在知道任何多磁带图灵机都可以由单个磁带机模拟。

一个例子

允许多个磁带大大扩展了图灵机程序的范围和功能。为了演示拥有多个磁带如何使我们的生活更轻松，下面是对一个接受练习2.48b中的语言的双磁带图灵机的描述。

L = {xyz | |x| = |z|, |y|≤|x|，且y至少包含两个1}

从磁带1的输入开始，空白磁带2，两个磁带的磁带头在它们磁带的开始。
扫描磁带1，确认输入至少包含6个符号。如果少于6个符号，停止并拒绝。否则，将磁带1上的磁带头倒回第一个单元。
从左到右扫描磁带1。从第一个字符开始，在第二个磁带上写一个1，并将第一个磁带上的磁带头向前移动三个单元。重复此操作，直到第一个磁带头下方出现空白。把两盘磁带的磁带头倒到开始。

重复以下操作，直到第二个磁带头下面出现空格：将磁带1上的当前字符替换为x，并将第一个磁带头向右移动，然后将第二个磁带头向右移动。

将第一个磁带上的磁带头移动到磁带上的最后一个字符。把第二盘磁带的磁带头倒回到磁带的开头。

重复以下操作，直到第二个磁带头下面出现空格：将磁带1上的当前字符替换为x，并将第一个磁带头向左移动，将第二个磁带头向右移动。

移动第一个磁带上的磁带头，记下你遇到的任何15。一旦你看到两个，停下来接受。如果你回到第一组x而没有看到两个15，停止并拒绝。

其他变体

请阅读3.2节，了解另外两个变体的讨论：非确定性图灵机（NTM）和枚举器。这两种情况都可以用一个确定性的单磁带图灵机来模拟。

丘奇-图灵论文

一旦我们有能力建立多磁带图灵机，我们就可以设计一台图灵机来做任何我们能想到的事情。这延伸到包括建立一个图灵机，可以复制冯·诺伊曼计算机的行为。冯·诺伊曼计算机由一个存储器和一个带有一组寄存器的中央处理器组成。一个模拟计算机的图灵机将有一个纸带来表示计算机的内存，和一个单独的纸带来表示每个寄存器的内容，包括一个程序计数器和地址寄存器。通过足够的工作，我们可以让图灵机模拟冯·诺伊曼机的获取-解释-求值循环，在这个循环中，冯·诺伊曼机从程序中获取下一条指令，解释机器语言指令，并通过操纵寄存器的内容来执行指令。这包括能够在寄存器上执行算术运算。

丘奇-图灵论文形式化了我们的直觉，即图灵机和传统计算机一样强大，因为传统计算机程序可以完成的任何事情，也可以由足够强大的图灵机程序完成。

通用图灵机

一个传统的计算机程序可以模拟图灵机的操作。特别是，不难想象构建一个图灵机模拟程序，它可以加载图灵机的描述以及图灵机的输入，然后模拟图灵机在处理输入时的行为。

我们刚刚看到图灵机可以模拟任何东西，所以我们可以把它扩展到想象一台图灵机，它可以模拟计算机程序，可以模拟任何图灵机在任何输入上运行。这样的结果是一个特别著名的图灵机，被称为通用图灵机。这是一台图灵机，它可以从任何其他图灵机的描述开始，并在其磁带上输入字符串，然后模拟其他机器在该输入上运行的行为。