1

我看过证明

ATM = {〈M,w〉 | M is a TM and M accepts w} is undecidable.

最初我们建造另一台图灵机

H 如果我们制造另一台图灵机，则输入<M,w>它接受M accept w otherwise reject

D which on input <M>
1.run H on <M,<M>>
2.output the opposite of what H outputs.

That is if H accepts reject and if H reject accept

我不明白作为输入的图灵机如何获得自己的描述然后拒绝它！你能解释一下吗？

4

2 回答 2

1

机器的输入没有特殊的状态，也没有任何要求。机器可以自由地拒绝自己。:)

因为我不想构建图灵机，这里有一个 Java 中的过度简化示例（它足够接近图灵完整性，它可以用来说明）：

class SelfReject {
    public boolean equals(Object other) {
        ...
    }

    public boolean accepts(Object input) {
        return (!this.equals(input));
    }
}

这种类型的对象将接受任何输入，但等于自身的对象除外。

于 2013-02-10T02:32:39.430 回答
1

我不确定你到底在哪里卡住了，所以我或多或少会尝试重申你的问题，希望能填补任何空白。

这个想法是，我们想要证明 ATM 是不可判定的，即没有 TM H，当给定任何另一个 TM M 和该 TM M 的任何其他输入 w 作为输入时，可以决定 TM M 是否会接受输入 w .

为了证明这样的 TM H 不存在，我们使假设存在这样的机器 H。至少有足够的幻想，这似乎不是一个太不合理的猜测。

下一个想法是仅仅通过推断这样一个 TM H 的存在会导致我们的论证出现矛盾的后果。因此证明我们最初的假设这样一个 TM H 可能存在一定是错误的。这意味着不存在遵循我们上面给出的规范的任何 TM H。

所以现在进入棘手的部分：因为我们假设存在一个 TM H，当给定任何 TM M 和该 TM M 的任何输入 w 作为输入时，可以决定 M 是否接受 w 没有人可以禁止我们只提供对机器 M 本身也将 w 输入到 M 本身。我们甚至假设我们可能会使用任何输入。

正如您在上面已经说过的，将任何机器作为输入输入到另一台机器的想法似乎不太容易实现，我们宁愿尝试在我们的第一个 TM 磁带上编码第二个 TM 的描述。

乍一看，似乎并不清楚是否真的可以对磁带上的任何 TM 进行编码，但实际上是有可能的。实现这一目标的可能方案之一是以数学家库尔特·哥德尔的名字命名的 Gödelisierung。

编码本身也经常被称为哥德尔数。

鉴于我们的 TM H，当给定 ANY TM M 的描述和对 M 的任何输入 w 作为输入决定 M 是否会接受 w 时，使用我们上面已经提到的自由，我们将简单地使用 TM M 的描述作为其自身的输入。

因此，构建一个 TM H'，当给定 TM M 的任何描述作为输入时，将决定 TM M 是否将其自己的描述作为输入工作是否接受。

正如您希望看到的那样，从我们的假设开始，上面指定的 TM H 我们没有做任何“禁止”的动作，如果我们使用我们新构建的 TM H' 来构建一个 TM D，当给定 ANY 时，我们肯定不会这样做TM M 作为输入只会返回与我们的机器 H' 相反的输出。

如果将任何 TM M 的描述作为输入，这个新的 TM D 将接受 > 如果 M 不接受它自己的描述作为输入，并且拒绝 > 如果 TM M 接受它自己的描述作为输入。

正如你所看到的，我们仍然可以自由地将任何（a 的描述）TM M 作为输入提供给 D，因此再次愉快地使用我们的自由，没有人可以禁止使用 TM D 本身的描述作为输入。

根据我们的构造，D 可以在任何 TM M 上工作作为输入，因此它肯定必须能够自行工作。

但正是这里出现了转折。事实上，要根据自己的描述作为输入来确定我们运行 D 的结果，我们只需要确定可能性：D 将接受或拒绝。

现在让我们检查这两种情况：

如果 D 接受它自己的描述作为我们构造的输入，这将意味着 D 将不得不拒绝，反之亦然。请记住，接受任何 TM 的 TM H' 接受它自己的描述作为输入，我们只是在构造中将其反转。

因此，我们发现了一个奇怪的事实，即当且仅当它接受它时，D 将不得不拒绝它自己的描述作为输入。

由于这显然不可能，您必须找到我们在构建中所犯错误的根源。沿着我们再次编造的整个路径，这使我们初步推断，如果 M 将接受 w，则存在一个 TM H 能够决定任何 TM M 和任何输入 w，这是我们假设 ATM 是可判定的暗示的。

于 2013-02-10T03:06:23.477 回答