1

我是可判定性的新手。我读了停止问题的停止问题，但没有得到任何它实际上暗示的东西。我已经搞砸了解释。

谁能给我任何合理的解释或至少一些细节，这会有很大帮助吗？

4

1 回答 1

3

您可以将图灵机视为一种可以执行程序的理论计算机。图灵机的程序由一组状态和这些状态之间的转换组成。在图灵机上运行的程序可以访问单个输入源，称为磁带，它有一些程序可以处理的字符串（可能是空的）。图灵机的所有程序要么return true（halt-accept），return false（halt-reject），要么return完全失败 - while (true) ; return true;。根据您的定义，机器也可能throw出现异常（崩溃）；但通常崩溃被认为是这样的事情try { /*crash*/ } catch (Exception) { return false; }，即崩溃意味着停止拒绝。

那么，停机问题是您是否可以为图灵机编写程序，其输入是图灵机的另一个程序和一些输入字符串，如果它有程序，则返回true或false（停止接受或停止拒绝）在提供的输入上被暂停，false否则返回（即，如果程序从不停止）。

事实证明，图灵机不存在这样的通用程序。假设确实存在一个，M. 给定输入m，i如果m停止则接受i，否则拒绝。我们可以制作另一个专门用来愚弄的程序M：

N(i)
1. if M(N, i) then loop forever;
2. otherwise return true

现在继续是否M适用于N：

  1. 假设M说N在 input 上停止i。然后N将永远循环，并且M将是错误的。

  2. 假设M说N在 input 上永远循环i。然后N将返回 true 并停止，因此M将是错误的。

在任何一种情况下，M都为我们的 给出了错误的答案N，并且由于我们除了假设它存在并解决了停机问题之外没有做出任何假设M，因此我们可以安全地得出结论，不存在解决停机问题的机器。

（如果不希望直接引用，可以作为输入M传递到程序中）。NM

于 2016-09-27T12:57:43.270 回答