ビジービーバー
ビジービーバー（英：busy beaver）とは、計算可能性理論で扱われるある種のチューリングマシンである。この名称は「仕事人間」を意味する英語の慣用句に由来する。ビジービーバーは空のテープから処理を開始し、可能な限り走り続けるが、最終的には停止する。これは停止するチューリングマシンのクラスが消費し得る時間と領域（テープ）の長さの上限を与える。
ビジービーバー関数はこの上限を数値化するものであり、計算不能関数の一例でもある。この関数はいかなる計算可能関数よりも急速に増大するということを証明できる。ビジービーバー関数の概念は、ティボール・ラドーによる1962年の論文 "On Non-Computable Functions" の中で、「ビジービーバー・ゲーム」という名称で初めて導入された。
ティボール・ラドーは、1962年の論文で以下のように「ビジービーバー・ゲーム」を導入した。
記号 {0, 1} と "n" 個の動作状態（それぞれ 1, 2, …, "n" で表すか、または "A", "B", "C" …などと書く）を持つチューリングマシンを考える。なお、動作状態にはもう一つ「停止」状態もあるとする。
彼が定義したチューリングマシンは次の通り。
さて、空のテープ（ここでは全てのセルに 0 が書かれたテープを「空テープ」と呼ぶ）から処理を始めよう。マシンを走らせて（遷移関数を繰り返し起動する）、マシンがいずれ停止したならば、テープに書かれた 1 の数を数えよう。
"n"-状態ビジービーバー（BB-"n" と書く）ゲームは、停止するまでにテープに 1 を最も多く出力するような "n"-状態チューリングマシンを見つけ出そう、というゲームである。
ラドーは次のように書いている。「この競技の参加希望者は、停止する "n"-状態チューリングマシンの記述と併せて、そのチューリングマシンが停止するまでに走行するステップ数を事前申請しなければならない。申請先は公正な審判員とし、審判員はその有効性を確認しなければならない。参加者が停止までに要するステップ数を申請することは重要である。なぜなら、もし申請がなく、そのチューリングマシンが停止しなかったら、審判員にはそのチューリングマシンが「永久に停止しない」のかどうかを証明する手段（アルゴリズム）がないからである。もし参加者が有限なステップ数とチューリングマシンを併せて申請するならば、審判員は（十分な時間は与えられるとして）それだけのステップ数にて実際にマシンが停止するかどうかを判定できる（とはいえ、審判員は巨大なステップ数のために勝者の判定には困難を覚えるかも知れない）。」
ビジービーバー関数 Σ("n") は、「状態」 (Turing-instructions) の個数を表す数字 n と空テープが与えられた時に、ビジービーバー・ゲームの「優勝」チューリングマシンが印字する 1 の個数として定義される。
ラドーは "n"-状態ビジービーバー・ゲームには well-defined な「優勝」マシンが存在することを示した：
"n" 個の状態と二つの記号を用いるチューリングマシンは有限個しかない（この場合は [4("n"+1)] 個）。更にこのうちの幾つかは停止することが自明である。すなわち、すべての "n" について、"n"-状態かつ 2-記号の停止するチューリングマシンが少なくとも一つ存在する。
ここで以下の定義を加える：
（"E" に含まれる）全ての停止する "M" について、σ("M") は非負整数であり、かつ、"E" は空でない有限集合なので、 全ての "n" について Σ("n") は well-defined な負でない有限の数である。
この Σ が ビジービーバー関数 であり、σ("M") = Σ("n") を満たす（つまり最大値を与える）ような "n"-状態 2-記号マシン "M" を ビジービーバー と呼ぶ。なお、"n"-状態ビジービーバーは一つとは限らない。つまり σ("M") = σ("M") = Σ("n") というようなことは有り得る。
ラドーは続けて、Σ を押さえ込むような計算可能関数は存在しないことを証明した。つまり、全ての計算可能関数 "f" について何らかの "n" が存在し（実は無限個の "n" があることを示せる）、"f(n)" < Σ("n") を満たす（証明は後述）。特に、Σ自身は計算不能である。
加えてこのことは、与えられた候補が優勝ビジービーバーであるかを判定するような一般的なアルゴリズムは存在しないことを意味する。なぜなら、もしそのようなアルゴリズムがあれば、全ての候補マシンを並べてテストするだけで Σ の値を容易に決定できてしまうからである。
入力として "n" を受け取り Σ("n") を計算するような単一のアルゴリズム "A" は存在しないものの（Σは計算不能なので）、"n" までの全ての自然数について Σ("n") を「計算」するようなアルゴリズム "A" は存在する（計算可能関数#例を参照のこと）。さらに、"n" が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 () を示すこともできる。"n" > 4 についての Σ("n") は未算出だが、4098 と formula_7 いう下限値がそれぞれ "n" = 5 と "n" = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している：
ここで指数の塔には 4096 が 166 回出現し、指数の塔の頂上に 4 が乗る。
シェン・リンは Σ(3) = 6 であることを証明した（ラドーとの共著論文 "Computer Studies of Turing Machine Problems" [1965年]）。
この証明に際し、彼は停止する "n"-状態チューリングマシンに関連するもう一つの極限関数である最大シフト数関数(maximum shifts function) を導入した。
以下を定義する：
これらのチューリングマシンは遷移関数を起動するごと（言い換えれば「ステップ」ごと）にシフトしなければならないので（「停止」状態に遷移する場合も含む）、最大シフト数関数は同時に最大ステップ数関数でもある。
さて、もし "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" の中で、ある種のマシンの集合を構成し次のことを示した。
これに対して、現在知られている Σ(6) の限界値は formula_14 であり、比較上大変小さい。
如何なる計算モデルにおいても、ビジービーバーの単純な類似物が存在する。例えば、n-状態 m-記号チューリングマシンへの一般化は次のような一般ビジービーバー関数の定義を導く。例として、これまで発見された中で最も長く走る 3-状態 3-記号マシンは、停止するまでに 119,112,334,170,342,540 ステップ走行する。 また、6-状態 2-記号マシンに対し、各ステップ毎にテープ上の値を反転する機能を付加した場合、最も長く走るマシンは 6,147 個の 1 を 47,339,970 ステップで印字する。したがって、"S"(6) ≧ 47,339,970 かつ Σ(6) ≧ 6,147 である。
同様に、レジスタマシンについても Σ 関数の類似物を定義できる。この場合は、所与の数の命令を実行した後に停止する時点で、いずれかのレジスタ上に存在できる最も大きな数、と言った形になる。
ビジービーバー関数はやり応えのある数学ゲームというだけでなく、深遠な応用を持つ。十分大きな "n" について "S"("n") の値が得られれば、それを用いて数多の数学上の未解決問題を機械的に解くことができる。
数学上の予想の中で、可算無限個のケースの中から反例を見つけ出せればその予想の否定を証明できるようなものを考える（例えばゴールドバッハ予想などが該当）。それらの予想について値を増分しながらテストするようなコンピュータプログラムを書く（ゴールドバッハ予想なら、4 以上の偶数全てについて、二つの素数の和として表せるかを順次調べる）。このプログラムを "n"-状態チューリングマシンでシミュレートする（もしくは、well-definedなプログラム言語であればその言語版のビジービーバー関数を定義できるので、そちらで代替してもよい）。もし反例（先の例で言えば、二つの素数の和で表せない偶数）を見付けたならば、停止して結果を表示する。反例が見付からなければプログラムは永遠に走り続ける（このプログラムは反例を見つけた場合にしか停止しないものとする）。
さて、今このプログラムは "n"-状態チューリングマシンでシミュレートしているので、もし "S"("n") がわかるなら、単にそのステップ数だけそのプログラムを走らせれば、そのプログラムが停止するのかどうかが（有限の時間内で）判明する。そして "S"("n") ステップだけ走った後でなおマシンが停止しないなら、それはもはや決して停止しないと言えるので、所与の予想には反例が存在しないことがわかる（二つの素数の和で表せない 4 以上の偶数は存在しない、等）。これはその予想が真であることを証明する。
このように、"S"("n") の特殊値（または上限値）を用いれば、理論的には様々な数学上の未解決問題を機械的に解ける。しかしながら、ビジービーバー問題に関してこれまで得られた結果に鑑みて、二つの理由からこれは現実的ではない。
"S"("n") が計算可能関数であると仮定し、"S"("n") を求めるチューリングマシンを "EvalS" と呼ぼう。このマシンは "n" 個の 1 が印字されたテープから処理を開始して、"S"("n") 個の 1 をテープ上に生成してから停止するものとする。併せて "Clean" という名のチューリングマシンを用意し、これはあらかじめテープ上に書かれた 1 をすべて消去するマシンとする。もう一つ "Double" という名のチューリングマシンを用意し、これは "n" + "n" を求めるマシンとする。つまり "n" 個の 1 が書かれたテープから処理を開始して、2"n" 個の 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 を印字し次にこれを二倍して、"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") もまた計算不能であることが従う。
3-状態ビジービーバーの状態表とその「走行」について、チューリングマシンの例()を参照。
以下の表は、次に挙げる値を生成するビジービーバーの実例である。Σ(1) と "S"(1)、Σ(2) と "S"(2)、Σ(3) (ただし "S"(3) は生成しない)、Σ(4) と "S"(4)、及び既知の最も優れた Σ(5) と "S"(5)、Σ(6) と "S"(6) の下限。
表の中で、列は現状態を表し、行はテープから読み込まれた現記号に対応する。表の中の三文字は（記述順に）テープに印字すべき記号、移動する方向、及び遷移先の状態を表す。Hは停止状態を示す。
各マシンは状態 A と空テープ（0 で埋まったテープ）から処理を開始する。従って最初にテープから読み込まれる記号は 0 である。
結果の見方：（下線位置から動作を開始し、太字の位置で停止する）
結果： 0 0 1 0 0 （1 ステップ、合計 1個の "1"）
結果： 0 0 1 1 1 1 0 0 (6 ステップ、合計 4個の "1")
結果： 0 0 1 1 1 1 1 1 0 0 (14ステップ、合計 6個の "1").
注：前の他のマシンと異なり、これはΣについて勝者だが、S については違う。(S(3) = 21)
結果： 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107ステップ、合計13個の "1")
結果： 47,176,870ステップにて8191個の "0" に混じって4098個の "1" を出力。
結果： ≈7.412 × 10 ステップにて ≈3.515 × 10個の "1" を出力。
以下の表で示すのは、一般ビジービーバー問題における"S"("n", "m") と Σ("n", "m") に関する既知の値または下限である。既知の正確な値は単なる数字で表し、既知の下限には大なりイコール(≧)を付けている。註："???"と書かれた場所の値は、その升の左方向と上方向に存在する中で最大の値（または下限）が下限となる。これらのマシンは未調査か、または一旦得られた下限がより小さいマシンに抜かれたために取り消されたかのいずれかである。
これらの値を達成したチューリングマシンの実例はHeiner MarxenのサイトかPascal Michelのサイトで見ることができる。これらのウェブサイトでは、他にもチューリングマシンに関する研究や正確な値についての証明などが紹介されている。
S("n","m") の値:
Σ("n","m") の値: