2

包含任意数量的磁带符号的图灵机 M 可以由仅包含三个磁带符号的 M' 模拟：{0, 1, B}（B = 空白）。

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

4

2 回答 2

7

第一步 - 从任何 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 的一元编码。然后我们机器的第一步是从一元编码转换为上述二进制编码。这可以只用两个符号来完成，但细节真的很难，我将再次强调它们。如果需要，您可以制定详细信息。

希望这可以帮助！

于 2011-01-27T19:28:10.273 回答
0

第一个很简单，想想电脑，二进制....

在第一个中，您可以将每个符号编码为 0,1 表示。

在第二个中，您可以做两件事：

  1. 将 B 视为 0 ......不管你怎么称呼它......然后你有一台 0,1 机器并且可以编码你想要的任何东西。

  2. 将符号编码为一系列符号，以 B 分隔。第 N 个符号将包含 N 个 1

于 2011-01-27T18:53:10.967 回答