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 回答