ビジービーバー・ゲーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
「ビジービーバー」の記事における「ビジービーバー・ゲーム」の解説
ティボール・ラドーは、1962年の論文で以下のように「ビジービーバー・ゲーム」を導入した。 記号 {0, 1} と n 個の動作状態（それぞれ 1, 2, …, n で表すか、または A, B, C …などと書く）を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。 彼が定義したチューリングマシンは次の通りである。 2つの方向に動作可能な無限長（または端のない）テープの上で動作する。 このマシンには「遷移関数」があり、次の2つの入力を取る。 マシンの現状態 現在の位置におけるテープ上の記号 そして3つの出力を持つ。テープの現在位置から読み出された記号を上書きするための記号（たまたま入力と同じ記号になる場合もある） テープ上を移動すべき方向（「左」または「右」） 遷移した後の状態（たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある） 以上より、このチューリングマシンは、その「プログラム」を次のような5つのタプル（組）の情報を有限個並べた表として書けるようなマシンである。 （現状態、現記号、次に書くべき記号、移動方向、次状態） このマシンは「停止」状態に達したときに停止する。 空のテープ（ここでは全てのセルに 0 が書かれたテープを「空テープ」と呼ぶ）をセットして処理を始める。マシンを走らせて（遷移関数を繰り返し起動する）、マシンがいずれ停止したならば、テープに書かれた 1 の数を数える。 n-状態ビジービーバー（BB-n と書く）ゲームは、停止するまでにテープに 1 を最も多く出力するような n-状態チューリングマシンを見つけ出す、というゲームである。 ラドーは次のように書いている。 この競技の参加希望者は、停止する n-状態チューリングマシンの記述と併せて、そのチューリングマシンが停止するまでに走行するステップ数を事前申請しなければならない。申請先は公正な審判員とし、審判員はその有効性を確認しなければならない。参加者が停止までに要するステップ数を申請することは重要である。なぜなら、もし申請がなく、そのチューリングマシンが停止しなかったら、審判員にはそのチューリングマシンが「永久に停止しない」のかどうかを証明する手段（アルゴリズム）がないからである。もし参加者が有限なステップ数とチューリングマシンを併せて申請するならば、審判員は（十分な時間は与えられるとして）それだけのステップ数にて実際にマシンが停止するかどうかを判定できる（とはいえ、審判員は巨大なステップ数のために勝者の判定には困難を覚えるかも知れない）。 — ティボール・ラドー
※この「ビジービーバー・ゲーム」の解説は、「ビジービーバー」の解説の一部です。
「ビジービーバー・ゲーム」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- ビジービーバー・ゲームのページへのリンク
