computer-science - 如何论证如果我们可以解决停机问题，那么我们就可以解决忙碌的海狸？

Question

这是我的任务之一。我有一个图灵机模拟，可以模拟一个忙碌的海狸功能。我已经做了一些关于证明这个问题的研究，但仍然没有得到它，所以我想也许你可以在这里帮助我。对我来说，这是一个很好的来源或如何论证这一点的例子。

Answer 1

BB 函数被定义为特定大小的图灵机可以执行并且仍然停止的最大步数。（另一种说法是，所有大小为 x 的图灵机要么在少于 BB(x) 步内停止，要么永远运行）。

假设您有一台复杂度为 x 的图灵机，那么您可以通过让它运行 BB(x) 个时间步来确定它是否会停止 - 如果到那时它还没有停止，那么根据定义它永远不会停止。

同样，如果您可以解决停机问题，您可以评估所有可能的大小为 x 的图灵机，消除那些不会停机的图灵机，并取 BB(x) 作为余数运行时间的最大值。

当然，BB(x) 是不可计算的——事实上，它的增长速度比你可以命名的任何可能的可计算函数都快——因此它甚至无法近似。

Answer 2

您可以在此处找到您要寻找的证明，在 Busy Beaver 问题不可计算的证明下方。