私たちは停止問題を解決することができれば、その後、私たちは忙しいビーバーを解決できると主張するには？

Question

これは私の割り当ての課題の一つです。私はhref="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow noreferrer">忙しいビーバー機能する

Answer 1

BB機能は、特定のサイズのチューリングマシンを実行し、依然として停止することができるステップの最大数であると定義されます。 （それを置くのもう一つの方法は、サイズxのすべてのチューリングマシンはどちらかBB未満（x）の段階で停止、または永久に実行されるということです）。

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

あなたは停止問題を解決することができれば、

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

もちろん、BB（x）は計算不可能である - そして実際にあなたが名前を付けることができすべての可能な計算可能関数よりも速く成長する - したがって、それも近似することができません。

。

Answer 2

あなたは以下の、ここのを求める証拠を見つけることができますビジービーバー問題がuncomputableであることを証明ます。