忙しいビーバー – 定義

導入

ビジー ビーバー(その名前はハンガリーの数学者Tibor Radóによって提案されました) は、計算不可能な関数の最初の例の 1 つです。ビジー ビーバーは、停止する前にリボンに最大「1」を書き込むn状態のチューリング マシンです。与えられた数nに対する「ビジー ビーバー」を決定することは、アルゴリズム的に解決できない問題です。実際には、10 を超える数nについてそれを解くことさえ期待できません。この抽象的な問題は、その起源からゲームによって説明されました。

忙しいビーバー ゲーム

「忙しいビーバー」と呼ばれるゲームを想像してみましょう。このゲームには 3 つのオブジェクトがあります。

• 無限のボックスで構成される「無限」のリボン
• リボンの各四角に0か1を書き込むことができる機械
• このマシンの動作を決定するn 個の命令のリスト

ゲームの目的は、次のルールに従って、停止する前にストリップにできるだけ多くの 1 を書き込める一連のルールを見つけることです。

ルール #1:マシンには有限数の状態があります (特別な STOP 状態を含む)。状態は次のように定義されます。

• 提供されている命令リスト内のその命令(これらを 1、2、3…n と呼びましょう)。
• 現在のボックス内のシンボル (0 または 1)。

次の状態は現在の状態によって一意に決定されます。より正確には、状態は次の状態に移行するために実行するアクションのリストをマシンに与えます (順序は重要です)。

• 無限テープへの書き込みアクション。マシンは 0 または 1 を書き込むことができます。
• 無限バンドを(左または右に)移動するアクション。
• ストップ（STOP状態への遷移）

ルール #2:指示リストはゲーム中に変更できません。

ルール #3:ゲームは、テープが 0 で埋められている命令 1 から始まります。

ルール #4:ゲームは遅かれ早かれ STOP 状態で終了します (したがって、無限の 1 のみを書き込む一連の命令を作成することは禁止されています)。

これらの規則により、マシンは 2 シンボルチューリング マシンになります。

例、n=2の場合

次の一連の手順を試してみましょう。

	命令 #1	命令 #2
ボックス読み取り値: 0	1を書きます リボンを右に移動します 手順2に進みます	1を書きます リボンを左に移動します 手順1に進みます
ボックスの読み取り数: 1	1を書きます リボンを左に移動します 手順2に進みます	1を書きます STOP状態に移行する

最初はステートメント 1 から開始し、リボンは 0 で埋められます (ここでは空のボックスで表されています)。

したがって、マシンは1 を書き込み、リボンを右に移動して命令2に進みます。

したがって、これらの命令をそのまま使用すると、マシンは1 を書き込み、リボンを左に移動して命令1に進みます。

など、次の状況に到達するまで続きます

この時点で、説明書に記載されているように、マシンは1を 4 つ書き込んだ後に停止します。これは、2 つのシンボルと 2 つの命令を使用して実行できる最善の方法です。

例、n=6の場合

	1	2	3	4	5	6
0	1を書きます リボンを右に移動します 手順2に進みます	0を書き込む リボンを右に移動します 手順3に進みます	1を書きます リボンを左に移動します 手順4に進みます	0を書き込む リボンを左に移動します 手順5に進みます	0を書き込む リボンを右に移動します 手順1に進みます	1を書きます リボンを左に移動します 手順1に進みます
1	0を書き込む リボンを左に移動します 手順6に進みます	0を書き込む リボンを右に移動します 手順4に進みます	1を書きます リボンを右に移動します 手順5に進みます	0を書き込む リボンを左に移動します 手順4に進みます	1を書きます リボンを右に移動します 手順3に進みます	1を書きます STOP状態に移行する

この命令セットを使用すると、3 x ^10,1730ステップでシンボル1を約 1.2 x ^10,865回書き込むことができます。その他の 6 命令マシンと正確な値については、Heiner Marxen のページを参照してください。