ビジービーバーとは？わかりやすく解説

ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。

ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、ティボール・ラドー（英語版）による1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。

ビジービーバー・ゲーム

ティボール・ラドーは、1962年の論文で以下のように「ビジービーバー・ゲーム」を導入した。

記号 {0, 1} と n 個の動作状態（それぞれ 1, 2, …, n で表すか、または A, B, C …などと書く）を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。

彼が定義したチューリングマシンは次の通りである。

2つの方向に動作可能な無限長（または端のない）テープの上で動作する。
このマシンには「遷移関数」があり、次の2つの入力を取る。
1. マシンの現状態
2. 現在の位置におけるテープ上の記号

そして3つの出力を持つ。

テープの現在位置から読み出された記号を上書きするための記号（たまたま入力と同じ記号になる場合もある）
テープ上を移動すべき方向（「左」または「右」）
遷移した後の状態（たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある）

以上より、このチューリングマシンは、その「プログラム」を次のような5つのタプル（組）の情報を有限個並べた表として書けるようなマシンである。

（現状態、現記号、次に書くべき記号、移動方向、次状態）

このマシンは「停止」状態に達したときに停止する。

空のテープ（ここでは全てのセルに 0 が書かれたテープを「空テープ」と呼ぶ）をセットして処理を始める。マシンを走らせて（遷移関数を繰り返し起動する）、マシンがいずれ停止したならば、テープに書かれた 1 の数を数える。

n-状態ビジービーバー（BB-n と書く）ゲームは、停止するまでにテープに 1 を最も多く出力するような n-状態チューリングマシンを見つけ出す、というゲームである。

ラドーは次のように書いている。

この競技の参加希望者は、停止する n-状態チューリングマシンの記述と併せて、そのチューリングマシンが停止するまでに走行するステップ数を事前申請しなければならない。申請先は公正な審判員とし、審判員はその有効性を確認しなければならない。参加者が停止までに要するステップ数を申請することは重要である。なぜなら、もし申請がなく、そのチューリングマシンが停止しなかったら、審判員にはそのチューリングマシンが「永久に停止しない」のかどうかを証明する手段（アルゴリズム）がないからである。もし参加者が有限なステップ数とチューリングマシンを併せて申請するならば、審判員は（十分な時間は与えられるとして）それだけのステップ数にて実際にマシンが停止するかどうかを判定できる（とはいえ、審判員は巨大なステップ数のために勝者の判定には困難を覚えるかも知れない）。 — ティボール・ラドー

ビジービーバー関数 Σ(n)

ラドーは n-状態ビジービーバー・ゲームには well-defined な「優勝」チューリングマシンが存在することを示した：

n 個の状態と2つの記号を用いるチューリングマシンは有限個しかない（この場合は [4(n+1)]²ⁿ 個^[1]）。さらにこのうちの幾つかは停止することが自明である。すなわち、すべての n について、n-状態かつ 2-記号の停止するチューリングマシンが少なくとも一つ存在する。

ビジービーバー関数 Σ(n) は、「状態」 (Turing-instructions^[2]) の個数を表す数字 n と空テープが与えられた時に、ビジービーバー・ゲームの「優勝」チューリングマシンが印字する 1 の個数を導く関数として定義される。

前述の性質（二方向の無限長のテープ、5タプルで定義される遷移関数など）を持ち、n-状態かつ2-記号の停止するチューリングマシンの有限で空でない集合を $E_{n}$
- ドイツ

[1]

[2]

ビジービーバーとは？ わかりやすく解説