使用单头磁带的双头磁带图灵机在线模拟

Question

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

Answer 1

以下是一种可能的方法：

1. 从一台多轨图灵机开始。如果你以前没有见过这一点，这是一个TM，其中每个磁带单元被分成多个不同的行，每一行可以容纳一个独立的符号。这相当于普通的图灵机，因为磁带单元中只能存储有限多个可能的符号组合，因此您可以构建磁带字母表，使每个组合具有不同的符号。
2. 让顶部磁道保存您的输入，并让底部磁道存储磁头的位置(通过标记空白来表示“无”，1表示“磁头1在这里”，2表示“磁头2在这里”，2表示“磁头2在这里”，3表示“两个磁头都在这里”。
3. 要模拟一个步骤，请扫描输入并找到标记。每次你这样做的时候，你都可以在你的有限状态控制中存储哪些符号在那些磁头下面。只有有限多的可能性。然后，重新扫描磁带并根据需要模拟移动磁头。

希望这能有所帮助！