ビジービーバー

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

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

ビジービーバー・ゲーム

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 前述の性質（二方向の無限長のテープ、5タプルで定義される遷移関数など）を持ち、n-状態かつ2-記号の停止するチューリングマシンの有限で空でない集合を ${\displaystyle E_{n}}$ と書く。
• チューリングマシン ${\displaystyle M}$ を空テープから走らせた後で、テープ上に残された 1 の個数を ${\displaystyle \sigma (M)}$ と書く。これは ${\displaystyle E_{n}}$ に含まれる全ての ${\displaystyle M}$ について定義される。
• このとき、あらゆる n-状態 2-記号チューリングマシンが書いた 1 の個数の中で最大の個数を表す関数${\displaystyle \Sigma (n)=\max\{\sigma (M)|M\in E_{n}\}}$ をビジービーバー関数とする。

（E_n に含まれる）全ての停止する M について、σ(M) は非負整数であり、かつ、E_n は空でない有限集合なので、 全ての n について Σ(n) は well-defined な負でない有限の数である。

　また、σ(M) = Σ(n) を満たす（つまり最大値を与える）ような n-状態 2-記号マシン M を ビジービーバー と呼ぶ。なお、n-状態ビジービーバーは一つとは限らない。つまり σ(M₁) = σ(M₂) = Σ(n) というようなことは有り得る。

Σ の計算不能性

ラドーは続けて、Σ を押さえ込むような計算可能関数は存在しないことを証明した。つまり、任意の計算可能関数 f に対して、f(n) < Σ(n) を満たすような n が存在することを証明した。

Σを押さえ込む計算可能関数は存在しないことから、特に Σ 自身が計算不能であることがわかる。これは、与えられた候補がビジービーバーであるかを判定する一般的なアルゴリズムが存在しないことを意味する。なぜなら、もしそのようなアルゴリズムがあれば、全ての候補マシンを並べてテストするだけで Σ の値を容易に決定できてしまうからである。

入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム A_n は、Σ(n) が決定可能である限り存在する（計算可能関数#例を参照のこと）。さらに、n が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 (オンライン整数列大辞典の数列 A028444) を示すこともできる。n > 4 についての Σ(n) は未算出だが、4098 と ${\displaystyle 10^{18267}}$ いう下限値がそれぞれ n = 5 と n = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している：

${\displaystyle \Sigma (12)\ \ \geq \ \ 6\ \cdot \ 4096^{4096^{4096^{~.~^{~.~^{~.~^{4096^{4}}}}}}}=6\cdot \left(4096\uparrow \right)^{166}4>4096\uparrow \uparrow 166}$

ここで指数の塔には 4096 が 166 回出現し、指数の塔の頂上に 4 が乗る。

最大シフト数関数 S(n)

シェン・リンは Σ(3) = 6 であることを証明した（ラドーとの共著論文 Computer Studies of Turing Machine Problems [1965年]）。

この証明に際し、彼は停止する n-状態チューリングマシンに関連するもう一つの極限関数である最大シフト数関数(maximum shifts function) を導入した。 以下を定義する：

• s(M) = E_n に含まれる全ての M について、停止するまでに M がシフトする回数
• ${\displaystyle S(n)=\max\{s(M)|M\in E_{n}\}}$ （あらゆる n-状態 2-記号チューリングマシンの中で最大のシフト回数）

これらのチューリングマシンは遷移関数を起動するごと（言い換えれば「ステップ」ごと）にシフトしなければならないので（「停止」状態に遷移する場合も含む）、最大シフト数関数は同時に最大ステップ数関数でもある。

さて、もし S(n) の値がわかるなら、全ての n-状態チューリングマシンを S(n) ステップだけ順次走らせて、テープ上に最多の 1 を印字して止まったマシンを見いだすことができる。それがビジービーバーであり、そのマシンが書いた 1 の数こそが Σ(n) ということになる（なぜなら、停止するすべての n-状態チューリングマシンは S(n) ステップ以内で停止するはずであるため）。

このように、最大シフト数関数の研究は、ビジービーバー関数の研究と密接に関連している。

既知の値

Σ(n) と S(n) の正確な値が判明しているのは n < 5 である場合に限られる。5-状態ビジービーバーについては、現時点で知られている優勝候補は 4,098 個の 1 を 47,176,870 ステップで出力するが（Heiner Marxen と Jurgen Buntrock、1989年）、他に約40個の非正則な振る舞いをするチューリングマシンが残されている。これらは停止しないと信じられているが、停止しないことの証明がいまだ得られていない。6-状態ビジービーバーの現時点における候補は 10¹⁸²⁶⁷ を超える 1 を 10³⁶⁵³⁴ を超えるステップにて出力する（Pavel Kropitz、2010年）。前述したように、これらのビジービーバーはすべて2-記号チューリングマシンである。

Milton Greenは、1964年の論文 "A Lower Bound on Rado's Sigma Function for Binary Turing Machines" の中で、ある種のマシンの集合を構成し次のことを示した。

$${\displaystyle {\begin{aligned}\Sigma (2k 4)&=\Sigma \left(2(k 2)\right)\\&>3\ \uparrow ^{k}3=\operatorname {hyper} (3,k 2,3)=3\ \uparrow ^{k 1}2\\&>A\left(k,k\right)=2\uparrow ^{k-2}\left(k 3\right)-3\\\end{aligned}}}$$ (${\displaystyle \uparrow }$ は クヌースの矢印表記 、${\displaystyle \operatorname {hyper} }$ は ハイパー演算子 であり、A は アッカーマン関数)

すなわち、

${\displaystyle \Sigma \left(2k\right)>\operatorname {hyper} (3,k,3)>A\left(k-2,k-2\right)=2\uparrow ^{k-4}\left(k 1\right)-3}$

従って、

${\displaystyle \Sigma (10)>3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}$ (高さは${\displaystyle 3^{27}={27}^{9}=7,625,597,484,987}$)、

先程のΣ(12) は $${\displaystyle {\begin{aligned}\Sigma (12)&>3\uparrow \uparrow \uparrow \uparrow 3\\&=3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 3^{3^{3}}\\&=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 7,625,597,484,987\\&\gg 6\cdot \left(4096\uparrow \uparrow \right)^{166}4\\&\gg 2\uparrow ^{4-2}\left(4 3\right)-3=2\uparrow ^{2}7-3\\&=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 4-3\\&=2^{2^{2^{2^{2^{4}}}}}-3=2^{2^{2^{2^{16}}}}-3=2^{2^{2^{65536}}}-3\\\end{aligned}}}$$

これに対して、現在知られている Σ(6) の限界値は ${\displaystyle 10^{18267}<3^{3^{3^{3}}}=3\uparrow \uparrow 4}$ であり、比較上大変小さい。

S(n) と Σ(n) が計算不能であることの証明

S(n) が計算可能関数であると仮定し、S(n) を求めるチューリングマシンを EvalS と呼ぼう。このマシンは n 個の 1 が印字されたテープから処理を開始して、S(n) 個の 1 をテープ上に生成してから停止するものとする。併せて Clean という名のチューリングマシンを用意し、これはあらかじめテープ上に書かれた 1 をすべて消去するマシンとする。もう一つ Double という名のチューリングマシンを用意し、これは n n を求めるマシンとする。つまり n 個の 1 が書かれたテープから処理を開始して、2n 個の 1 をテープ上に生成したのち停止する。 さて、このような状況で、Double | EvalS | Clean という複合マシンを用意して、このマシンの状態個数を n₀ と書く。さらに、 Create_n₀ という名のチューリングマシンを用意し、これは空テープに対して n₀ 個の 1 を印字するものとする。このマシンが n₀ 個の状態を持つようにするのは容易である（i 状態は 1 を印字し、テープヘッドを右に一つ移動し、状態を i 1 に切り替える。ただし、n₀ に達したならば停止する）。n₀ と n₀ の和 (n₀ n₀) を N と書こう。

ここで今度は BadS という名の複合マシンを用意し、この内容は Create_n₀ | Double | EvalS | Clean とする。このマシンは N 状態を持つことに注意する。空テープから処理を開始し、まず n₀ 個の一連の 1 を印字し次にこれを2倍にして、N 個の一連の 1 を生成する。BadS はそれから S(N) 個の 1 をテープに書き、最後に全ての 1 を消去して停止する。しかしながら、この消去処理は少なくとも S(N) ステップだけ動作するので、BadS の動作時間は S(N) よりも厳密に大きいことになり、これは関数 S(n) の定義と矛盾する。

Σ(n) が計算不能であることも同様にして証明できる。上の証明に出てきた EvalS マシンを EvalΣ マシンに替え、Clean を Increment ―テープ上最初に出てくる 0 を探して順次 1 で置き換える単純なチューリングマシン―で代替すればよい。

S(n) が計算不能であることは、停止問題に帰着して証明することも容易である。S(n) は停止するチューリングマシンが実行可能な最大ステップ数なので、それを越えて走り続けるマシンは決して停止しない。したがって、与えられた任意の n 状態チューリングマシンを S(n) ステップだけ走らせてみて、それがいまだ停止しないなら、それはもはや決して停止しない。以上より、S(n) の値が計算できれば停止問題が解けてしまうことになるが、停止問題が計算不能であることは別途証明されているので、S(n) もまた計算不能であることが従う。

S(n) の決定不能性

n が十分に大きい場合、S(n) は単に計算不能であるだけでなく、ある種の公理系の下では決定不能である。

2016年、Yedidia と Aaronson は 7910-状態の、ZF と、幾つかの追加公理である stationary Ramsey property (SRP) とで構成される公理系が矛盾する場合のみ停止するチューリングマシンを明示的に作成し、ゲーデルの不完全性定理により ZF SRP の下では S(7910) の値が決定不能であることを証明した。 後に結果は改良され、同年 O’Rear は SRP に依存せず、ZF (厳密には ZF よりわずかに弱いが、無矛盾性が ZF および ZFC と一致する公理系) が矛盾する場合にのみ停止する 1919-状態のチューリングマシンを作成して、ZF の下では S(1919) の値が証明できないことを示した。 状態数は翌年 O’Rear 自身によって 748-状態に、2023年 には Riebel により 745-状態にまで改善された。

つまり 745 以上の n と、一般的な数学の基礎となる公理系である ZFC の下において、S(n) の値は決定不能である。

応用

ビジービーバー関数はやり応えのある数学ゲームというだけでなく、深遠な応用を持つ。十分大きな n について S(n) の値が得られれば、それを用いて数多の数学上の未解決問題を機械的に解くことができる。

予想の中で、可算無限個のケースの中から反例を見つけ出せればその予想の否定を証明できるようなものを考える（例えばゴールドバッハ予想などが該当）。それらの予想について値を増分しながらテストするようなコンピュータプログラムを書く（ゴールドバッハ予想なら、4 以上の偶数全てについて、2つの素数の和として表せるかを順次調べる）。このプログラムを n-状態チューリングマシンでシミュレートする（もしくは、well-definedなプログラム言語であればその言語版のビジービーバー関数を定義できるので、そちらで代替してもよい）。もし反例（先の例で言えば、2つの素数の和で表せない偶数）を見付けたならば、停止して結果を表示する。反例が見付からなければプログラムは永遠に走り続ける（このプログラムは反例を見つけた場合にしか停止しないものとする）。

さて、今このプログラムは n-状態チューリングマシンでシミュレートしているので、もし S(n) がわかるなら、単にそのステップ数だけそのプログラムを走らせれば、そのプログラムが停止するのかどうかが（有限の時間内で）判明する。そして S(n) ステップだけ走った後でなおマシンが停止しないなら、それはもはや決して停止しないと言えるので、所与の予想には反例が存在しないことがわかる（2つの素数の和で表せない 4 以上の偶数は存在しないなど）。これはその予想が真であることを証明する。

このように、S(n) の特殊値（または上限値）を用いれば、理論的には様々な数学上の未解決問題を機械的に解ける。しかしながら、ビジービーバー問題に関してこれまで得られた結果に鑑みて、以下の2つの理由からこれは現実的ではない。

• ビジービーバー関数（および最大シフト数関数）の値を証明するのは極めて難しい。これまでに証明できたのは 5 状態にも満たない極端に小さなマシンに関する値のみだが、実用的なマシンを構築するには少なくとも 20～50 状態は必要だろうと推測される。
• ビジービーバー関数（および最大シフト数関数）の値は非常に速く増大する。S(6) > 10³⁶⁵³⁴ の段階で既に、特殊な専用チューニングを施さなければシミュレートを走り切らせることがおぼつかない状況である。また、${\displaystyle S(18)>\Sigma (18)}$ > グラハム数であることが知られている。したがって、例えば S(30) あたりの値がわかったとしても、いかなるマシンであれ、それだけのステップ数だけ走らせる方法などまったく存在しないだろう。

ビジービーバーであるチューリングマシンの例

3-状態ビジービーバーの状態表とその「走行」について、チューリングマシンの例(en)を参照。

以下の表は、次に挙げる値を生成するビジービーバーの実例である。Σ(1) と S(1)、Σ(2) と S(2)、Σ(3) (ただし S(3) は生成しない)、Σ(4) と S(4)、Σ(5) と S(5)、および既知の最も優れた Σ(6) と S(6) の下限。

表の中で、列は現状態を表し、行はテープから読み込まれた現記号に対応する。表の中の3文字は（記述順に）テープに印字すべき記号、移動する方向、および遷移先の状態を表す。Hは停止状態を示す。

各マシンは状態 A と空テープ（0 で埋まったテープ）から処理を開始する。従って最初にテープから読み込まれる記号は 0 である。

結果の見方：（下線位置から動作を開始し、太字の位置で停止する）

1-状態, 2-記号

結果： 0 0 1 0 0 （1 ステップ、合計 1個の "1"）

2-状態, 2-記号

結果： 0 0 1 1 1 1 0 0 (6 ステップ、合計 4個の "1")

3-状態, 2-記号

結果： 0 0 1 1 1 1 1 1 0 0 (14ステップ、合計 6個の "1").

注：前の他のマシンと異なり、これはΣについて勝者だが、S については違う。(S(3) = 21)

4-状態, 2-記号

結果： 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107ステップ、合計13個の "1")

5-状態, 2-記号

結果： 47,176,870ステップにて8191個の "0" に混じって4098個の "1" を出力。

現時点における 6-状態, 2-記号の最高記録者

結果：1 0 1 1 1 1 1 1 ... 1 1 1 (≧10↑↑15ステップ後に、 "10" の後に "1" が10↑↑15 個以上連続して続く出力で停止)

一般化

如何なる計算モデルにおいても、ビジービーバーの単純な類似物が存在する。例えば、n-状態 m-記号チューリングマシンへの一般化は次のような一般ビジービーバー関数の定義を導く。

1. Σ(n, m)：空テープを与えられた n-状態 m-記号マシンが、停止するまでに印字しうる 0 でない記号の最大個数。
2. S(n, m)：空テープを与えられた n-状態 m-記号マシンが停止するまでに実行しうる最大ステップ数。

例として、これまで発見された中で最も長く走る 3-状態 3-記号マシンは、停止するまでに 119,112,334,170,342,540 ステップ走行する。 また、6-状態 2-記号マシンに対し、各ステップ毎にテープ上の値を反転する機能を付加した場合、最も長く走るマシンは 6,147 個の 1 を 47,339,970 ステップで印字する。したがって、S_RTM(6) ≧ 47,339,970 かつ Σ_RTM(6) ≧ 6,147 である。

同様に、レジスタマシンについても Σ 関数の類似物を定義できる。この場合は、所与の数の命令を実行した後に停止する時点で、いずれかのレジスタ上に存在できる最も大きな数、と言った形になる。

S(n, m) と Σ(n, m) の値と下限について

以下の表で示すのは、一般ビジービーバー問題におけるS(n, m) と Σ(n, m) に関する既知の値または下限である。既知の正確な値は単なる数字で表し、既知の下限には大なりイコール(≧)を付けている。註："???"と書かれた場所の値は、その升の左方向と上方向に存在する中で最大の値（または下限）が下限となる。これらのマシンは未調査か、または一旦得られた下限がより小さいマシンに抜かれたために取り消されたかのいずれかである。

これらの値を達成したチューリングマシンの実例はHeiner MarxenのサイトかPascal Michelのサイトで見ることができる。これらのウェブサイトでは、他にもチューリングマシンに関する研究や正確な値についての証明などが紹介されている。

S(n,m) の値:

Σ(n,m) の値:

関連項目

• コルモゴロフ複雑性

脚注

参考文献

外部リンク

• The page of Heiner Marxen, who, with Jurgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• Pascal Michel's Historical survey of busy beaver results which also contains best results and some analysis.
• The page of Penousal Machado's Genetic Beaver Project uses Evolutionary Computation to find new candidates to the busy beaver Problem
• Definition of the class RTM - Reversal Turing Machines, simple and strong subclass of the TMs.
• The "Millennium Attack" at the Rensselaer RAIR Lab on the busy beaver Problem.
• Aaronson, Scott (1999), Who can name the biggest number?
• Weisstein, Eric W. "Busy Beaver". mathworld.wolfram.com (英語).
• Busy Beaver by Hector Zenil, Wolfram Demonstrations Project.