如果，假设，繁忙的海狸数量是“小”，你怎么能“解决”停止问题？

Question

我读到，如果bb（n）没有比所有整数的所有可计算序列更快地增长，您可以解决停止问题并违反图规定的定理。

我正试图弄清楚你如何专门做到这一点。一个明显的可能性是建立一个N状态图灵机，该机器寻找一个无法可判定的问题的解决方案，然后只是等待它通过BB（n）转换。这应该是可行的，因为BB（n）在这种情况下很小，并且超越它将证明这是机器环游的。

但这不是一个令人满意的答案，因为肯定的脱名性不是关于程序在实践中的可行性，但它是否在理论上是可判定的 - 如果计算机足够强大，可以在我们当前的宇宙中实现这一点BB（n）非常大？我们不应该假设机器独立于数字理论吗？

Answer 1

要遵循您的策略，我们需要自信，我们在 $ bb（n）$ 上有一个上限。更具动画，如果 $ f $ 是 $ f（n）\ ge bb（n）$ ，然后来自 $ f $ 我们可以计算停止问题：给定 $ n $ -state machine ，为 $ f（n）$ - many步骤运行它。

由于暂停问题不是可计算，这意味着没有这样的 $ f $ 是可计算的;这是一个“全球”现象。 NO 特定 $ bb $ 太大而无法使用，而是增长率 $ bb（n）$ 可防止我们从整个上限序列，一个用于每个 $ n $ 。作为低级类比：

没有多项式函数，始终高于 $ exp（n）= 2 ^ $ 。当然，这不是因为 $ exp $ 的单个值太大，而是因为所有输入中功能的整体行为 。

Answer 2

但这不是一个令人满意的答案，因为肯定的脱名性不是关于程序在实践中的可行性，但它是否在理论上是可判定的 - 如果计算机足够强大，可以在我们当前的宇宙中实现这一点bb（n）非常大？

问题不是那么多，BB（n）非常大，问题是它不是可计算的。您所谓的决策程序无法正常工作，因为它不知道我们是否超过了BB（n）转换。