1

我最近遇到了停止问题矛盾证明。在证明中，我们必须向图灵机提供程序的副本和输入的副本，以决定该程序是否在输入时停止。在矛盾中，为什么一定要程序作为程序和输入？对不起，如果这听起来令人困惑。我可以简单地给机器输入一个程序和一个随机输入并得出相同的结论。

谁能告诉我为什么？有没有我没有想到的具体原因？

4

1 回答 1

0

首先让我回到证明本身。

HALT_TM 无法确定

假设任何机器都有一个采用字符串形式的描述。让HALT_TM = {<M, w>| M is a TM and M halts on input w}和A_TM = {<M,w>| M is a TM and accepts w}。在这里，我假设我们知道这A_TM是不可判定的（证明可以通过对角化来完成，并意识到由于语言比图灵机多，并且给定的 TM 仅决定一种语言，因此某些语言未决定）。

假设矛盾HALT_TM是可判定的，这意味着我们D为这种语言处理了一个判定器。然后我们就可以建造一台机器M来决定A_TM。在 input上<M', w>，M执行以下操作：

  • D在输入上运行<M',w>
  • 如果D拒绝，则拒绝，否则继续运行M'（w直到它停止，我们知道这是因为D没有拒绝！）
  • 如果M'接受，就接受，如果拒绝，就拒绝。

在那里我们看到了与我们的假设的矛盾

通用图灵机

现在您的问题的核心：您实际上提供了M任何有效的机器描述M'，不一定是<M>它本身。请记住，TM 和“程序”实际上是等价的：有关更多详细信息，请参阅这个不错的答案。引用相同的答案：“图灵机是算法的形式模拟”。图灵机的一个强大之处在于它们可以被编码为字符串，允许另一个图灵机（称为“通用图灵机”）执行它们。因为给定的机器是一种算法，所以您会看到您实际上正在为您的“顶级” TM 提供一个程序和您选择的输入。

于 2017-04-27T21:48:48.833 回答