图灵机元素差异问题

Question

所以语言如下：

E = {＃x1＃x2 ...＃xi，其中字母表是{0,1} *，没有字符串可以是另一个字符串的副本}

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

Answer 1

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

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

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