algorithm - 图灵机元素唯一性问题

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)，然后对剩余的输入重复整个过程

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