algorithm - 图灵机元素区别问题

Question

所以语言如下：

E = {#x1#x2...#xi 其中字母是 {0,1}* 并且没有字符串可以与另一个字符串重复 }

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

标签： algorithmtheoryautomataturing-machines

Answer 1

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

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

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