图灵机元素区别性问题

Question

所以语言如下：

E = {#x1#x2...#xi 其中字母表是 {0,1}* 并且任何字符串都不能是另一个字符串的副本 }

我正在尝试为此创建状态图，但在此之前，我就想出了解决它的算法，但我遇到的问题是每当我比较前两个字符串时，我都必须用"x"标记每个字符，那么我将如何恢复第一个字符串？就像第一次我比较 x1 和 x2，当我完成时，在 x2 中，x1 中的所有字符都会标有"x"，所以当我继续使用 x3 时，x1 没有什么可比较的。

Answer 1

不要用 x 标记所考虑的符号，而是使用与被标记的符号相对应的特殊符号标记它们。因此，与其将 x 写为 0，将 x 写为 1，不如将 a 写为 0，b 写为 1。事实上，继续使用符号 c 和 d 来替换"我需要检查的最早的东西"中的值，以便您可以检查所有对。使用此策略的图灵机的高级描述如下：

1. 开始读取第一个输入，将 0 替换为 c，将 1 替换为 d
转到第二个输入，
2. 如果第二个输入到目前为止是匹配的，则为 0 写 a，为 1 写 b，然后继续。如果不匹配，我们知道这些输入不匹配，我们可以开始比较其他对。将要检查的输入更改为仅 a 和 b，并将第一个输入重置为仅 0 和 1。
3. 重复此过程，跳过已经存在的所有 A 和 B 以检查涉及第一项的所有对。
4. 一旦你检查了所有涉及第一项的对，把它划掉(也许使用x)，然后在剩余的输入上重复整个过程

这将检查所有对并按预期工作。正如您正确推测的那样，关键是能够重建部分输入，这意味着您需要在磁带字母表中添加额外的符号。毫不犹豫地引入磁带符号 - 它们是免费的，永远不会受到伤害。