complexity-theory - 使用单头磁带的双头磁带图灵机的在线仿真

Question

我有一个问题，但我还没有找到答案。我需要使用单头磁带对双头磁带图灵机进行在线模拟。我在网上找到了一些文章，说明一个单头磁带不足以解决这个问题，应该使用两个单头磁带进行模拟，但我无法准确模拟两个-head TM 使用这些单头磁带。有没有关于如何做到这一点的想法？谢谢，

Answer 1

这是一种可能的方法：

1. 从多轨图灵机开始。如果您以前没有见过这个，这是一个 TM，其中每个磁带单元被分割成多个不同的行，每个行可以包含一个独立的符号。这相当于普通的图灵机，因为只有有限多种可能的符号组合可以存储在磁带单元中，因此您可以构建磁带字母表，为每个符号设置不同的符号。

2. 让顶部轨道保存您的输入，并让底部轨道存储磁带头的位置（通过将空白标记为“无”，1 表示“磁带头 1 在这里”，2 表示“磁带头 2 在这里”，以及3 表示“两个磁带头都在这里”。

3. 要模拟一个步骤，请扫描输入并找到标记。每次这样做时，您都可以在有限状态控制中存储这些磁带磁头下的符号。只有有限的多种可能性。然后，重新扫描磁带并根据需要模拟移动磁头。

希望这可以帮助！