ビジービーバー

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

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

1. ビジービーバー・ゲーム
--------------

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

記号 {0, 1} と //n// 個の動作状態を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。

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

2つの方向に動作可能な無限長テープの上で動作する。
このマシンには「遷移関数」があり、次の2つの入力を取る。
マシンの現状態
現在の位置におけるテープ上の記号そして3つの出力を持つ。
テープの現在位置から読み出された記号を上書きするための記号
テープ上を移動すべき方向
遷移した後の状態以上より、このチューリングマシンは、その「プログラム」を次のような5つのタプルの情報を有限個並べた表として書けるようなマシンである。
このマシンは「停止」状態に達したときに停止する。空のテープをセットして処理を始める。マシンを走らせて、マシンがいずれ停止したならば、テープに書かれた 1 の数を数える。

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

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

2. ビジービーバー関数 Σ
---------------------

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

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

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

前述の性質を持ち、//n//-状態かつ2-記号の停止するチューリングマシンの有限で空でない集合を と書く。
チューリングマシン を空テープから走らせた後で、テープ上に残された 1 の個数を と書く。これは に含まれる全ての について定義される。
このとき、あらゆる //n//-状態 2-記号チューリングマシンが書いた 1 の個数の中で最大の個数を表す関数 をビジービーバー関数とする。全ての停止する //M// について、σ は非負整数であり、かつ、//En// は空でない有限集合なので、 全ての //n// について Σ は well-defined な負でない有限の数である。

　また、σ = Σ を満たすような //n//-状態 2-記号マシン //M// を ビジービーバー と呼ぶ。なお、//n//-状態ビジービーバーは一つとは限らない。つまり σ = σ = Σ というようなことは有り得る。

3. Σ の計算不能性
-----------

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

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

入力として //n// を受け取り Σ を計算するような単一のアルゴリズム //A// は存在しないものの、//n// までの全ての自然数について Σ を「計算」するようなアルゴリズム //An// は、Σ が決定可能である限り存在する。さらに、//n// が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ = 0, Σ = 1 を示すのは難しくないし、次第に困難にはなるが、Σ = 4 と Σ = 6 と Σ = 13  を示すこともできる。//n// > 4 についての Σ は未算出だが、4098 と いう下限値がそれぞれ //n// = 5 と //n// = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している：

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

4. 最大シフト数関数 //S//
------------------------

シェン・リンは Σ = 6 であることを証明した。

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

//s// = //En// に含まれる全ての //M// について、停止するまでに //M// がシフトする回数
これらのチューリングマシンは遷移関数を起動するごとにシフトしなければならないので、最大シフト数関数は同時に最大ステップ数関数でもある。

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

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

5. 既知の値
-------

Σ と //S// の正確な値が判明しているのは //n// < 5 である場合に限られる。5-状態ビジービーバーについては、現時点で知られている優勝候補は 4,098 個の 1 を 47,176,870 ステップで出力するが、他に約40個の[1]振る舞いをするチューリングマシンが残されている。これらは停止しないと信じられているが、停止しないことの証明がいまだ得られていない。6-状態ビジービーバーの現時点における候補は 1018267 を超える 1 を 1036534 を超えるステップにて出力する。前述したように、これらのビジービーバーはすべて2-記号チューリングマシンである。

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

すなわち、

従って、

、先程のΣ は

これに対して、現在知られている Σ の限界値は であり、比較上大変小さい。

6. //S// と //Σ// が計算不能であることの証明
--------------------------------------------

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

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

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

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

7. //S// の決定不能性
----------------------

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

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

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

8. 応用
-----

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

数学上の予想の中で、可算無限個のケースの中から反例を見つけ出せればその予想の否定を証明できるようなものを考える。それらの予想について値を増分しながらテストするようなコンピュータプログラムを書く。このプログラムを //n//-状態チューリングマシンでシミュレートする。もし反例を見付けたならば、停止して結果を表示する。反例が見付からなければプログラムは永遠に走り続ける。

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

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

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

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

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

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

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

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

結果の見方：

9.1. 1-状態, 2-記号
---------------

{| class="wikitable"! width="20px" | !! A |- ! 0 | 1,R,H |- ! 1 | 未使用 |}

結果： 0 0 1 0 0

9.2. 2-状態, 2-記号
---------------

{| class="wikitable"! width="20px" | !! A !! B |- ! 0 | 1,R,B || 1,L,A |- ! 1 | 1,L,B || 1,R,H |}

結果： 0 0 1 1 1 1 0 0 

9.3. 3-状態, 2-記号
---------------

{| class="wikitable"! width="20px" | !! A !! B !! C |- ! 0 | 1,R,B || 0,R,C || 1,L,C |- ! 1 | 1,R,H || 1,R,B || 1,L,A |}

結果： 0 0 1 1 1 1 1 1 0 0 .

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

9.4. 4-状態, 2-記号
---------------

{| class="wikitable"! width="20px" | !! A !! B !! C !! D |- ! 0 | 1,R,B || 1,L,A || 1,R,H || 1,R,D |- ! 1 | 1,L,B || 0,L,C || 1,L,D || 0,R,A |}

結果： 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 

9.5. 現時点にて 5-状態, 2-記号の勝者と信じられているもの
----------------------------------

{| class="wikitable"! width="20px" | !! A !! B !! C !! D !! E |- ! 0 | 1,R,B || 1,R,C || 1,R,D || 1,L,A || 1,R,H |- ! 1 | 1,L,C || 1,R,B || 0,L,E || 1,L,D || 0,L,A |}

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

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

{| class="wikitable"! width="20px" | !! A !! B !! C !! D !! E !! F |- ! 0 | 1,R,B || 1,R,C || 1,L,D || 1,R,E || 1,L,A || 1,L,H |- ! 1 | 1,L,E || 1,R,F || 0,R,B || 0,L,C || 0,R,D || 1,R,C |}

結果： ≈7.412 × 1036534 ステップにて ≈3.515 × 1018267個の "1" を出力。

10. 一般化
-------

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

Σ：空テープを与えられた //n//-状態 //m//-記号マシンが、停止するまでに印字しうる 0 でない記号の最大個数。
//S//：空テープを与えられた //n//-状態 //m//-記号マシンが停止するまでに実行しうる最大ステップ数。例として、これまで発見された中で最も長く走る 3-状態 3-記号マシンは、停止するまでに 119,112,334,170,342,540 ステップ走行する。 また、6-状態 2-記号マシンに対し、各ステップ毎にテープ上の値を反転する機能を付加した場合、最も長く走るマシンは 6,147 個の 1 を 47,339,970 ステップで印字する。したがって、//S//RTM ≧ 47,339,970 かつ ΣRTM ≧ 6,147}} である。

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

10.1. //S// と Σ の値と下限について
-----------------------------------------------------

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

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

S の値:

{| class="wikitable"! ! width="120px" | 2-状態 ! width="120px" | 3-状態 ! width="120px" | 4-状態 ! width="120px" | 5-状態 ! width="120px" | 6-状態 |- ! 2-記号 | align="right" | 6 | align="right" | 21 | align="right" | 107 | align="right" | ≧ 47,176,870 | align="right" | ≧ 7.4 × 1036534 |- ! 3-記号 | align="right" | 38 | align="right" | ≧   119,112,334,170,342,540 | align="right" | ≧ 1.0 × 1014072 | align="center" | ??? | align="center" | ??? |- ! 4-記号 | align="right" | ≧ 3,932,964 | align="right" | ≧ 5.2 × 1013036 | align="center" | ??? | align="center" | ??? | align="center" | ??? |- ! 5-記号 | align="right" | ≧ 1.9 × 10704 | align="center" | ??? | align="center" | ??? | align="center" | ??? | align="center" | ??? |- ! 6-記号 | align="right" | ≧ 2.4 × 109866 | align="center" | ??? | align="center" | ??? | align="center" | ??? | align="center" | ??? |}

Σ の値:

{| class="wikitable"! ! width="120px" | 2-状態 ! width="120px" | 3-状態 ! width="120px" | 4-状態 ! width="120px" | 5-状態 ! width="120px" | 6-状態 |- ! 2-記号 | align="right" | 4 | align="right" | 6 | align="right" | 13 | align="right" | ≧ 4,098 | align="right" | ≧ 3.5 × 1018267 |- ! 3-記号 | align="right" | 9 | align="right" | ≧ 374,676,383 | align="right" | ≧ 1.3 × 107036 | align="center" | ??? | align="center" | ??? |- ! 4-記号 | align="right" | ≧ 2,050 | align="right" | ≧ 3.7 × 106518 | align="center" | ??? | align="center" | ??? | align="center" | ??? |- ! 5-記号 | align="right" | ≧ 1.7 × 10352 | align="center" | ??? | align="center" | ??? | align="center" | ??? | align="center" | ??? |- ! 6-記号 | align="right" | ≧ 1.9 × 104933 | align="center" | ??? | align="center" | ??? | align="center" | ??? | align="center" | ??? |}

11. 関連項目
--------

コルモゴロフ複雑性

12. 脚注
------

13. 参考文献
--------

Rado, Tibor , //On non-computable functions//, Bell System Technical Journal, Vol. 41, No. 3 , pp. 877-884. ラドーはこの中でビジービーバー問題を初めて定義し、それが計算不能であることと如何なる計算可能関数よりも急速に増大することを証明した。
Lin, Shen and Rado, Tibor , [4], Journal of the ACM, Vol. 12, No. 2 , pp. 196-212. リンはラドーの下で博士課程を学ぶ学生だった。この論文はリンの学位論文の一部として書かれた。リンは、すべての3-状態 2-記号チューリングマシンは、21ステップで停止しないなら、以後決して停止しないことを証明し、そこから Σ = 6 かつ S = 21 であることを示した。
Brady, Allen H. , [5], Mathematics of Computation, Vol. 40, No. 162 , pp. 647-665. ブレイディは Σ = 13 かつ S = 107 であることを証明している。ブレイディは停止しない 3-状態 2-記号チューリングマシンについて2つの新たなカテゴリを定義した。「クリスマス・ツリー」と「カウンタ」である。彼はあるコンピュータプログラムを用いて、107ステップを越えて走行するマシンは、27個を除いてすべてがクリスマス・ツリーかカウンタの変種であることを示し、つまり停止しないことを証明した。残りの27個については、ブレイディ自身の手作業によって停止しないことが証明された。
Machlin, Rona and Stout, Quentin F. , [6], Physica D, No. 42 , pp. 85-98. マチリンとスタウトはビジービーバー問題を取り上げ、ビジービーバーを特定するための様々な技法を展開している。彼らは 4-状態 2-記号 以下のマシンについて既知であるすべての S の値を用いて、チャイティンの停止確率 の変種の値を推定した。
Marxen, Heiner and Buntrock, Jurgen , [7], Bulletin of the EATCS, No 40 , pp. 247-251. マルクセンとバントロックはΣ の下限が 4098 かつ S の下限が 47,176,870 であることを示し、彼らがマシンを見付けるために用いた手法を詳述しつつ、他の多くのマシンが停止しないことを証明した。
Green, Milton W. , //A Lower Bound on Rado's Sigma Function for Binary Turing Machines//, in Preceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design, pp. 91-94. グリーンは状態の個数全てについてマシンを再帰的に構成し、それらの得点を計算する帰納的関数を導いて、Σ の下限を与えた。この関数が増大する速さはアッカーマン関数のそれと比較できる。
Busy beaver programs are described by Alexander Dewdney in //Scientific American//, August 1984, pages 19-23, also March 1985 p. 23 and [8].
Dewdney, Alexander K. //A computer trap for the busy beaver, the hardest working Turing machine//, Scientific American, 251 , 10-17, 1984.
Chaitin, Gregory J. , [9], In T. M. Cover and B. Gopinath, //Open Problems in Communication and Computation//, Springer, 1987, pp. 108-112.
Brady, Allen H. , //The Busy Beaver Game and the Meaning of Life//, p 237-254, appearing in Herken, Rolf ., //The Universal Turing Machine: A Half-Century Survey//, 2nd edition , Springer-Verlag, Wien New York. この中でブレイディはこの問題の歴史を紹介し「ビジービーバー・ゲーム」と呼んだ。彼は他のゲームについても言及している