turing-machines - 可以构造只有两个磁带符号的图灵机吗？

Question

包含任意数量的纸带符号的图灵机 M 可以通过仅包含三个纸带符号的 M' 来模拟:{0, 1, B}(B = 空白)。

M 可以用只有两个纸带符号的 M"来模拟吗，比如说 {1, B}？

Answer 1

第一步 - 从任何 TM 到只有 1 和 0 的 TM - 并不像您想象的那么难，但也不像其他人所说的那么容易。这个想法是为字母表中的每个符号开发一个固定长度的二进制编码。然后更新有限状态控制，以便在每一步 TM 扫描适当的位数，决定移动的方式和写入哪个符号，写入新符号的二进制表示，然后重复。这可以通过拥有一个巨大的有限状态控制来完成，我将把细节留给读者，因为回顾它是如何工作的真的很迂腐。 :-)。需要注意的一个细节是，在此构造中，您将空白符号表示为一系列空白，其长度与您发明的二进制符号相同。

要仅使用 1 和 B 来实现 TM，您可以使用类似的技巧。首先，将 TM 缩减为仅使用 1、0 和 B。我们将再次将符号集缩减为较小的一个，但我们必须更巧妙地进行操作，因为纸带上有无限多的空白它。我们将使用以下编码:

1. 11编码数字1
2. 1B编码数字0
3. BB 编码一个空白。

当我们使用这种编码方案运行 TM 时，如果我们走过之前访问过的磁带的末尾，我们将遇到无限多的空白符号，幸运的是，它们与我们对空白符号的编码相对应。

唯一的挑战是如何对这个新 TM 的输入进行编码，以便我们可以将其转换为上述格式。由于 TM 输入中不能出现空格，因此输入必须以一元编码。那么我们规定对于旧机器的任意二进制串w，新机器的输入应该是数字1w的一元编码。然后我们让机器的第一步是从一元编码转换为上面的二进制编码。这可以只用两个符号来完成，但细节真的很难，我要再次赌上它们。如果需要，您可以制定详细信息。

希望这对您有所帮助!