如何论证如果我们能够解决停机问题，那么我们就能解决忙碌的海狸问题？
这是我的任务之一。我有一个图灵机模拟，可以模拟 busy beaver 函数。我已经做了一些关于证明这个问题的研究，但仍然不明白，所以我想也许你可以在这里帮助我。对我来说，一个很好的资源或者如何论证这一点的例子会很好。
This is one of the tasks of my assignment. I have a Turing machine simulation which can simulate a busy beaver function. I have done some research about proving this problem, but still don't get it so I guess maybe you can help me here. A good source for me to go to or example of how to argue this would be good.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
BB 函数被定义为特定大小的图灵机可以执行并且仍然停止的最大步数。 （另一种说法是，所有大小为 x 的图灵机要么会在小于 BB(x) 的步骤内停止，要么永远运行）。
假设你有一个复杂度为 x 的图灵机，那么你可以通过让它运行 BB(x) 时间步来确定它是否会停止 - 如果到那时它还没有停止，那么根据定义它永远不会停止。
同样，如果您可以解决停止问题，您可以评估所有可能的大小为 x 的图灵机，消除那些不停止的图灵机，并取 BB(x) 作为余数的运行时间的最大值。
当然，BB(x) 是不可计算的 - 事实上，它的增长速度比任何可能的可计算函数都要快 - 因此它甚至无法被近似。
The BB function is defined to be the maximum number of steps a Turing machine of a particular size can carry out and still halt. (Another way of putting it is that all Turing machines of size x will either halt in less than BB(x) steps, or run forever).
Assuming you have a Turing machine of complexity x, then you could determine whether it would halt or not by letting it run for BB(x) time-steps - if it hadn't halted by then, then by definition it never will.
Equally, if you could solve the halting problem, you could evaluate all possible Turing machines of size x, eliminate those that don't halt, and take BB(x) to be the maximum of the run times of the remainders.
Of course, BB(x) is non-computable - and in fact grows faster than any possible computable function you could name - hence it cannot even be approximated.
您可以在此处找到您想要的证据，位于以下证据的下方：忙碌海狸问题是不可计算的。
You can find the proof you seek here, below the proof that the Busy Beaver problem is uncomputable.