|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ ビー ： [びー] (n) bee, (n) bee ・ ビーバー ： [びーばー] 【名詞】 1. beaver 2. (n) beaver
ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。 ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、ティボール・ラドーによる1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。 ==ビジービーバー・ゲーム== ティボール・ラドーは、1962年の論文で以下のように「ビジービーバー・ゲーム」を導入した。 記号 と ''n'' 個の動作状態（それぞれ 1, 2, …, ''n'' で表すか、または ''A'', ''B'', ''C'' …などと書く）を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。 彼が定義したチューリングマシンは次の通り。 *二つの方向に動作可能な無限長（または端のない）テープの上で動作する。 *このマシンには「遷移関数」があり、次の二つの入力を取る。 ::#マシンの現状態 ::#現在の位置におけるテープ上の記号 :そして三つの出力を持つ。 ::#テープの現在位置から読み出された記号を上書きするための記号（たまたま入力と同じ記号になる場合もある） ::#テープ上を移動すべき方向（「左」または「右」） ::#遷移先の状態（たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある） :以上より、このチューリングマシンは、その「プログラム」を次のような５つ組の情報を有限個並べた表として書けるようなマシンである。 :（現状態、現記号、次に書くべき記号、移動方向、次状態） *このマシンは「停止」状態に達したときに停止する。 さて、空のテープ（ここでは全てのセルに 0 が書かれたテープを「空テープ」と呼ぶ）から処理を始めよう。マシンを走らせて（遷移関数を繰り返し起動する）、マシンがいずれ停止したならば、テープに書かれた 1 の数を数えよう。 ''n''-状態ビジービーバー（BB-''n'' と書く）ゲームは、停止するまでにテープに 1 を最も多く出力するような ''n''-状態チューリングマシンを見つけ出そう、というゲームである。 ラドーは次のように書いている。「この競技の参加希望者は、停止する ''n''-状態チューリングマシンの記述と併せて、そのチューリングマシンが停止するまでに走行するステップ数を事前申請しなければならない。申請先は公正な審判員とし、審判員はその有効性を確認しなければならない。参加者が停止までに要するステップ数を申請することは重要である。なぜなら、もし申請がなく、そのチューリングマシンが停止しなかったら、審判員にはそのチューリングマシンが「永久に停止しない」のかどうかを証明する手段（アルゴリズム）がないからである。もし参加者が有限なステップ数とチューリングマシンを併せて申請するならば、審判員は（十分な時間は与えられるとして）それだけのステップ数にて実際にマシンが停止するかどうかを判定できる（とはいえ、審判員は巨大なステップ数のために勝者の判定には困難を覚えるかも知れない）。」 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ビジービーバー」の詳細全文を読む スポンサード リンク
|