如何争辩说，如果我们能够解决停机问题，那么我们就可以解决忙海狸？

Question

这是我分配的任务之一。我有一个图灵机的模拟，可以模拟忙海狸功能。我已经做了要证明这个问题的一些研究，但还是不明白这一点，所以我想也许你能帮助我在这里。一个很好的来源，我去或示例如何认为这将是一件好事。

Answer 1

在BB函数被定义为一个特定大小的图灵机可以进行，并且仍然停止的步骤的最大数目。 （把它的另一种方式是，大小为x的所有图灵机要么停止在小于BB（x）的步骤，或永远运行）。

假设你有复杂x的图灵机，那么你可以决定是否将通过让它运行BB停止或没有（x）的时间步长 - 如果不是通过再停止，然后通过定义它从来没有将

同样的，如果你能解决停机问题，你可以评估大小为x的所有可能的图灵机，消除那些不制止，并采取BB（X）为最大余数的运行时间。

当然，BB（x）是非可计算 - 并且实际上长得比任何可能的可计算函数你可以命名更快 - 因此它甚至不能近似

Answer 2

您可以找到你寻求这里证明，之下证明该忙海狸问题是不可计算。