仮説的に、忙しいビーバー番号が「小さい」の場合、停止の問題をどのように「解決する」ことができますか？

Question

私は、BB（N）が整数のすべての計算可能なシーケンスよりも速く成長しなかった場合、あなたは停止問題を解決し、TURINGの定理と矛盾することができます。

私はあなたが特にこれを行うことができる方法を理解しようとしています。1つの明らかな可能性は、未確定の問題に対する解決策を探すN状態チューリングマシンを構築することであり、次にそれがBB（N）遷移を通過させるのを待つだけです。このシナリオでは、これは実現可能であるはずです。

しかし、確実に決定されていないプロシージャーが実際にどのように実行されているかが理論的であるかどうかではないので、これは満足のいく答えではありませんが、理論的には決定的なものであるかどうか - 私たちの現在の宇宙でこれを実装できるようにするのに十分強力だった場合BB（N）は非常に大きいですか？マシンが代わりに数理論とは無関係であると仮定してはいけませんか？

Answer 1

あなたが概説する戦略に従うために、私たちは $ bb（n）$ に上限を持っている先験的に自信を持っている必要があります。 $ f $ の場合、 $ f（n）\ ge bb（n）$ 、 $ f $ から停止問題を計算できます。 $ n $ -Stateマシン $ f（n）$ -manyステップのためにそれを実行してください。

停止問題がでないため、このような $ f $ が計算可能であることを意味します。これは「グローバルな」現象です。 $ bb $ のの値は大きすぎるが、むしろ成長率 class="math-container"> $ bb（n）$ 上限のシーケンス全体を持つことを防ぎます。 $ n $ ごとに1つずつ。低レベルの類推として：

$ exp（n）= 2 ^ n $ を常に上回る多項式関数はありません。もちろん、これは $ exp $ の個々の値が大きすぎるが、むしろ全入力にわたる関数の全体的な動作のためであるためではなく 。

Answer 2

しかし、確実に決定されていないプロシージャーが実際にどのように実行されているかが理論的であるかどうかではないので、これは満足のいく答えではありませんが、理論的には決定的なものであるかどうか - 私たちの現在の宇宙でこれを実装できるようにするのに十分強力だった場合BB（N）は非常に大きいですか？

問題は、BB（N）が非常に大きいほど問題は計算不可能であるということです。あなたの想定された決定手続きは、BB（N）の遷移を超えているかどうかわからないので機能しません。