computer-science - 停止問題を解決できれば、忙しいビーバーも解決できるとどのように主張できますか?

Question

これは私の割り当てのタスクの 1 つです。忙しいビーバー関数をシミュレートできるチューリングマシンシミュレーションがあります。この問題を証明するためにいくつかの調査を行いましたが、まだ理解できていないので、ここで私を助けてくれると思います. 私が行く良い情報源、またはこれが良いと主張する方法の例.

Answer 1

BB関数は、特定のサイズのチューリングマシンが実行して停止できる最大ステップ数として定義されます。（別の言い方をすれば、サイズxのすべてのチューリングマシンはBB（x）ステップ未満で停止するか、永久に実行されます）。

複雑さxのチューリングマシンがあると仮定すると、BB（x）タイムステップで実行させることで、停止するかどうかを判断できます。それまでに停止していなかった場合、定義上、停止することはありません。

同様に、停止の問題を解決できれば、サイズxの可能なすべてのチューリングマシンを評価し、停止しないチューリングマシンを排除し、BB（x）を残りの実行時間の最大値にすることができます。

もちろん、BB（x）は計算不可能であり、実際、名前を付けることができる計算可能な関数よりも速く成長するため、近似することさえできません。

Answer 2

ビジービーバーの問題が計算できないという証拠の下に、ここで探している証拠があります。