0

我想问几个关于以下证明的问题。证明最初来自教科书，然后是下面关于 stackoverflow 的问题。

这个证明，停止问题‍​是不可判定的，是如何工作的？

问题一：

下面的证明本质上是否使 H 成为其输入机器的模拟器？

换句话说，说 H = M 与证明中的以下描述之间有重要区别吗？

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept w.}

问题2：

我的以下评论如何正确或不正确？

我认为停止问题是决定给定机器是否会停止而不管其输出（接受/拒绝）的问题。如果存在停止问题的解决方案，它必须是分析源代码的东西，如编译器/反编译器/反汇编器，而不是实际运行它。如果它需要运行它，显然它永远不会确定“否”的答案。

注意到证明中的明显问题，整个证明似乎没有显示停止问题的不可判定性。

相反，证明似乎表明了这一点：以下算法不会停止：

    boolean D()
    {
        return not D();
    }

以下是 Sipser 从 Intro to the Theory of Computation 重新键入的相关证明。

停机问题无法确定

现在我们准备证明定理 4.11，语言的不可判定性

ATM = {[M,w] | M 是一个 TM 并且 M 接受 w}。

证明：我们假设ATM是可判定的，得到一个矛盾。假设 H 是 ATM 的决策者。在输入时，M 是一个 TM，w 是一个字符串，如果 M 接受 w，H 会停止并接受。此外，如果 M 未能接受 w，H 将停止并拒绝。换句话说，我们假设 H 是一个 TM，其中

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept w.}

现在我们构造一个新的图灵机 D，其中 H 作为子程序。当 M 的输入是它自己的描述时，这个新的 TM 调用 H 来确定 M 做什么。一旦 D 确定了这个信息，它就会做相反的事情。也就是说，如果 M 接受则拒绝，如果 M 不接受则接受。以下是对 D 的描述。

D = "On input [M], where M is a TM:
1. Run H on input [M, [M]].
2. Output the opposite of what H outputs; that is, if H accepts, reject and if H rejects, accept."

不要对根据自己的描述运行机器的想法感到困惑！这类似于以自身作为输入运行程序，在实践中偶尔会发生这种情况。例如，编译器是翻译其他程序的程序。Pascal 语言的编译器本身可能是用 Pascal 编写的，因此在其自身上运行该程序是有意义的。总之，

D([M]) = { accept if M does not accept [M]
       = { reject if M accepts [M]

当我们以自己的描述作为输入运行 D 时会发生什么> 在这种情况下，我们得到：

D([D]) = {accept if D does not accept [D]
       = {reject if D accepts [D]

不管 D 做什么，都是强制反其道而行之，这显然是矛盾的。因此，TM D 和 TM H 都不存在。

4

1 回答 1

0

换句话说，说 H = M 与证明中的以下描述之间有重要区别吗？

H机器被称为通用图灵机（UTM），能够模拟任何其他图灵机，包括它自己。

如果 M 是像 H 这样的通用图灵机，可以说 H = M，否则这会很奇怪。

我认为停止问题是决定给定机器是否会停止而不管其输出（接受/拒绝）的问题。如果存在停止问题的解决方案，它必须是分析源代码的东西，如编译器/反编译器/反汇编器，而不是实际运行它。如果它需要运行它，显然它永远不会确定“否”的答案。

这就是为什么证明是基于矛盾的，而且很难理解。基本上它首先假设存在这样一台机器，它对任何给定的输入回答“是”或“否”。[假设]

我们称这台机器为 Q。假设 Q 是有效的并且它是一个 UTM，它可以模拟另一台机器 S，按照以下步骤工作：

  1. S 读取输入（程序及其输入）
  2. S 复制它刚刚读取的输入
  3. S 调用 Q 传递复制的输入
  4. S 等待 Q 回答（根据我们的假设，它总是会）

现在让我们想象一下输入 Q(S, S)。Q 将接收程序 S 并且 S 的参数是 S 本身。这个输入将使 S 无限期地调用 Q 并且永远不会停止。

由于 Q 和 S 是合法程序，但有一种输入使 Q 永远不会停止，所以 Q 是一台无法制造的机器，因此无法确定程序 S 是否停止。因此，我们有证据表明停止问题是不可判定的。

Sipser 很好地解释了这一点。现在再读一遍，看看你是否明白这个想法:)

现在，再次回答你的问题。图灵机是我们表示问题的最强大的机器。作为识别机器，它必须通过输入并运行算法来确定它是否有效。不运行算法就不可能知道算法的输出。

编译器只是语法和少量语义的翻译器。它无法预见人们将如何使用该程序以及输出将是什么。

于 2012-12-10T02:57:13.877 回答