ビジービーバーのソースを表示

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

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

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

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

彼が定義したチューリングマシンは次の通りである。
*2つの方向に動作可能な無限長（または端のない）テープの上で動作する。
*このマシンには「遷移関数」があり、次の2つの入力を取る。
*#マシンの現状態
*#現在の位置におけるテープ上の記号
:そして3つの出力を持つ。
:#テープの現在位置から読み出された記号を上書きするための記号（たまたま入力と同じ記号になる場合もある）
:#テープ上を移動すべき方向（「左」または「右」）
:#遷移した後の状態（たまたま現状態と同じ状態になる場合はあるし、または「停止」状態を指す可能性もある）
:以上より、このチューリングマシンは、その「プログラム」を次のような5つの[[タプル]]（組）の情報を有限個並べた表として書けるようなマシンである。
:（現状態、現記号、次に書くべき記号、移動方向、次状態）
*このマシンは「停止」状態に達したときに停止する。

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

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

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

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

''n'' 個の状態と2つの記号を用いるチューリングマシンは有限個しかない（この場合は [4(''n''+1)]<sup>2''n''</sup> 個<ref>記号の個数を ''m'' とおけば、[2''m''(''n''+1)]<sup>''mn''</sup>。

チューリングマシンを表す状態遷移表（縦に記号、横に状態を並べる）において、1つのセルの取りうる値の候補が、左右の動きの候補が2個、出力する記号の候補がm個、停止を含んだ遷移先の状態の候補がn+1個なので、[2''m''(''n''+1)]<sup>''mn''</sup>になる</ref>）。さらにこのうちの幾つかは停止することが自明である。すなわち、すべての ''n'' について、''n''-状態かつ 2-記号の停止するチューリングマシンが少なくとも一つ存在する。

'''ビジービーバー関数 Σ(''n'')''' は、「状態」 (Turing-instructions<ref>訳注：Turing-instructions：チューリングマシンのプログラム。ここで言う「状態」は、テープから読み取った記号ごとに対応する動作指示を記述する形を採るので、すなわちプログラムでもある。[[#ビジービーバーであるチューリングマシンの例]]を参照</ref>) の個数を表す数字 n と空テープが与えられた時に、ビジービーバー・ゲームの「優勝」チューリングマシンが印字する 1 の個数を導く関数として定義される。

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

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

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

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

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

入力として ''n'' を受け取り Σ(''n'') を計算するような単一のアルゴリズム ''A'' は存在しないものの、''n'' までの全ての自然数について Σ(''n'') を「計算」するようなアルゴリズム ''A<sub>n</sub>'' は、Σ(''n'') が決定可能である限り存在する（[[計算可能関数#例]]を参照のこと）。さらに、''n'' が十分に小さいならば、ビジービーバー関数の特殊値を[[計算複雑性理論#イントラクタブル|実用的に]]計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 ({{OEIS|id=A028444}}) を示すこともできる。''n'' > 4 についての Σ(''n'') は未算出だが、4098 と <math>10^{18267}</math> いう下限値がそれぞれ ''n'' = 5 と ''n'' = 6 について得られている。n = 12 については、Dewdney[1984] は次のいささか大きな下限を紹介している：
:<math>\Sigma(12) \ \ \geq \ \ 6 \ \cdot \ 4096^{4096^{4096^{~.~^{~.~^{~.~^{4096^{4}}}}}}}=6 \cdot \left(4096 \uparrow \right)^{166}4> 4096 \uparrow \uparrow 166 </math>
ここで指数の塔には 4096 が 166 回出現し、指数の塔の頂上に 4 が乗る。

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

この証明に際し、彼は停止する ''n''-状態チューリングマシンに関連するもう一つの極限関数である'''最大シフト数関数'''(maximum shifts function) を導入した。
以下を定義する：
* ''s''(''M'') = ''E<sub>n</sub>'' に含まれる全ての ''M'' について、停止するまでに ''M'' がシフトする回数
* <math>S(n) = \max \{ s(M) | M \in E_n \}</math> （あらゆる ''n''-状態 2-記号チューリングマシンの中で最大のシフト回数）

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

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

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

==既知の値==
Σ(''n'') と ''S''(''n'') の正確な値が判明しているのは ''n'' &lt; 5 である場合に限られる。5-状態ビジービーバーについては、現時点で知られている優勝候補は 4,098 個の 1 を 47,176,870 ステップで出力するが（Heiner Marxen と Jurgen Buntrock、1989年）、他に約40個の[http://skelet.ludost.net/bb/nreg.html 非正則な]振る舞いをするチューリングマシンが残されている。これらは停止しないと信じられているが、停止しないことの証明がいまだ得られていない。6-状態ビジービーバーの現時点における候補は 10<sup>18267</sup> を超える 1 を 10<sup>36534</sup> を超えるステップにて出力する（Pavel Kropitz、2010年）。前述したように、これらのビジービーバーはすべて2-記号チューリングマシンである。

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

<math display=block>
\begin{align}
\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{align}
</math>
(<math>\uparrow</math> は [[クヌースの矢印表記]] 、<math>\operatorname{hyper}</math> は [[ハイパー演算子]] であり、''A'' は [[アッカーマン関数]])

すなわち、

:<math>\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</math>

従って、

:<math>\Sigma(10) > 3 \uparrow\uparrow\uparrow 3 = 3 \uparrow\uparrow 3^{3^3} = 3^{3^{3^{\cdot^{\cdot^{\cdot^3}}}}}</math> (高さは<math>3^{27} = {27}^{9} = 7,625,597,484,987</math>)、
先程のΣ(12) は
<math display=block>
\begin{align}
\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{align}
</math>

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

==''S''(''n'') と ''Σ''(''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''<sub>0</sub> と書く。さらに、 ''Create_n<sub>0</sub>'' という名のチューリングマシンを用意し、これは空テープに対して ''n''<sub>0</sub> 個の 1 を印字するものとする。このマシンが ''n''<sub>0</sub> 個の状態を持つようにするのは容易である（''i'' 状態は 1 を印字し、テープヘッドを右に一つ移動し、状態を ''i'' + 1 に切り替える。ただし、''n''<sub>0</sub> に達したならば停止する）。''n''<sub>0</sub> と ''n''<sub>0</sub> の和 (''n''<sub>0</sub> + ''n''<sub>0</sub>) を ''N'' と書こう。

ここで今度は ''BadS'' という名の複合マシンを用意し、この内容は ''Create_n<sub>0</sub>'' | ''Double'' | ''EvalS'' | ''Clean'' とする。このマシンは ''N'' 状態を持つことに注意する。空テープから処理を開始し、まず ''n''<sub>0</sub> 個の一連の 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) の値が決定不能であることを証明した<ref>{{cite report | arxiv=1605.04343 | author=Adam Yedidia and Scott Aaronson | title=A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory | institution=MIT | type=Technical Report | date=May 2016 | bibcode=2016arXiv160504343Y }}</ref><ref name="AaronsonFrontier" />。
後に結果は改良され、同年 O’Rear は SRP に依存せず、ZF (厳密には ZF よりわずかに弱いが、[[無矛盾|無矛盾性]]が ZF および ZFC と一致する公理系<ref name="RiebelJuly2023" />) が矛盾する場合にのみ停止する 1919-状態のチューリングマシンを作成して<ref name=Aaronson3>{{cite news|url=https://scottaaronson.com/blog/?p=2741|title=Three announcements|date=2016-05-03|work=Shtetl-Optimized blog|access-date=2023-09-29}}</ref><ref>{{Cite web | url=https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm | title=GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things.| website=[[GitHub]]| date=2016-05-16 |access-date=2023-09-29}}</ref>、ZF の下では ''S''(1919) の値が証明できないことを示した。
状態数は翌年 O’Rear 自身によって 748-状態に<ref name="AaronsonFrontier">{{Cite web|url=https://scottaaronson.com/papers/bb.pdf|title=The Busy Beaver Frontier |access-date=2023-09-29}}</ref><ref>{{Cite web | url=https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf2.tm | title=GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things.| website=[[GitHub]]| date=2017-08-08 |access-date=2023-09-29}}</ref>、[[2023年]] には Riebel により 745-状態にまで改善された<ref name="AaronsonJuly2023">{{Cite web | url=https://scottaaronson.blog/?p=7388 | title=Life, blogging, and the Busy Beaver function go on |date=2023-07-05|access-date=2023-09-29}}</ref><ref name="RiebelJuly2023">{{Cite web|url=https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf|title=The Undecidability of BB(748)|access-date=2023-09-29}}</ref>。

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

==応用==
ビジービーバー関数はやり応えのある数学ゲームというだけでなく、深遠な応用を持つ。十分大きな ''n'' について ''S''(''n'') の値が得られれば、それを用いて数多の[[数学上の未解決問題]]を機械的に解くことができる<ref>[[グレゴリー・チャイティン]]、1987年</ref>。

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

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

このように、''S''(''n'') の特殊値（または上限値）を用いれば、理論的には様々な数学上の未解決問題を機械的に解ける。しかしながら、ビジービーバー問題に関してこれまで得られた結果に鑑みて、以下の2つの理由からこれは現実的ではない。
*ビジービーバー関数（および最大シフト数関数）の値を証明するのは極めて難しい。これまでに証明できたのは 5 状態にも満たない極端に小さなマシンに関する値のみだが、実用的なマシンを構築するには少なくとも 20～50 状態は必要だろうと推測される。
*ビジービーバー関数（および最大シフト数関数）の値は非常に速く増大する。''S''(6) > 10<sup>36534</sup> の段階で既に、特殊な専用チューニングを施さなければシミュレートを走り切らせることがおぼつかない状況である。また、<math>S(18) > \Sigma(18)</math>  > [[グラハム数]]であることが知られている<ref>{{Cite web |title=The nineteenth Busy Beaver number is greater than Graham's Number! |url=https://googology.fandom.com/wiki/User_blog:Wythagoras/The_nineteenth_Busy_Beaver_number_is_greater_than_Graham%27s_Number! |website=Googology Wiki |access-date=2023-01-03 |language=en}}</ref>。したがって、例えば ''S''(30) あたりの値がわかったとしても、いかなるマシンであれ、それだけのステップ数だけ走らせる方法などまったく存在しないだろう。

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

3-状態ビジービーバーの状態表とその「走行」について、[[チューリングマシンの例#3-状態ビジービーバー|チューリングマシンの例]]([[:en:Turing machine examples#3-state Busy Beaver|en]])を参照。

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

表の中で、列は現状態を表し、行はテープから読み込まれた現記号に対応する<ref>訳注：例えば現状態がAで入力が記号0なら、0行A列が交差する位置のマス目の中身を実行する</ref>。表の中の3文字は（記述順に）テープに印字すべき記号、移動する方向、および遷移先の状態を表す。<span style="color:blue">'''H'''</span>は停止状態を示す。<ref>訳注：Rはright(右) Lはleft(左) <span style="color:blue">'''H'''</span>はhalt(停止)を示す</ref>

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

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

===1-状態, 2-記号===

:{| class="wikitable"
! width="20px" | !! A
|-
! 0
| 1,R,<span style="color:blue">'''H'''</span>
|-
! 1
| 未使用
|}

'''結果：''' 0 0 <u>1</u>  '''0''' 0 （1 ステップ、合計 1個の "1"）

===2-状態, 2-記号===

:{| class="wikitable"
! width="20px" | !! A !! B
|-
! 0
| 1,R,'''B''' || 1,L,'''A'''
|-
! 1
| 1,L,'''B''' || 1,R,<span style="color:blue">'''H'''</span>
|}

'''結果：''' 0 0 1 1 '''<u>1</u>''' 1 0 0 (6 ステップ、合計 4個の "1")

===3-状態, 2-記号===

:{| class="wikitable"
! width="20px" | !! A !! B !! C
|-
! 0
| 1,R,'''B''' || 0,R,'''C''' || 1,L,'''C'''
|-
! 1
| 1,R,<span style="color:blue">'''H'''</span> || 1,R,'''B''' || 1,L,'''A'''
|}

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

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

===4-状態, 2-記号===

:{| class="wikitable"
! width="20px" | !! A !! B !! C !! D
|-
! 0
| 1,R,'''B''' || 1,L,'''A''' || 1,R,<span style="color:blue">'''H'''</span> || 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 <u>1</u> 1 1 1 0 0 (107ステップ、合計13個の "1")

=== 5-状態, 2-記号 <ref>{{Cite web |title=[July 2nd 2024] We have proved "BB(5) = 47,176,870" |url=https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237 |website=The Busy Beaver Challenge |date=2024-07-02 |access-date=2024-07-11 |language=en}}</ref> ===

:{| class="wikitable"
! width="20px" | !! A !! B !! C !! D !! E
|-
! 0
| 1,R,'''B''' || 1,R,'''C''' || 1,R,'''D''' || 1,L,'''A''' || 1,R,<span style="color:blue">'''H'''</span>
|-
! 1
| 1,L,'''C''' || 1,R,'''B''' || 0,L,'''E''' || 1,L,'''D''' || 0,L,'''A'''
|}

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

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

:{| class="wikitable"
! width="20px" | !! A !! B !! C !! D !! E !! F
|-
! 0
| 1,R,'''B''' || 1,R,'''C''' || 1,L,'''C''' || 0,L,'''E''' || 1,L,'''F''' || 0,R,'''C'''
|-
! 1
| 0,L,'''D'''|| 0,R,'''F''' || 1,L,'''A'''|| 1,R,<span style="color:blue">'''H'''</span>|| 0,R,'''B'''|| 0,R,'''E'''
|}

'''結果：'''1 '''0''' 1 1 1 1 1 1 ... 1 1 1 (≧10↑↑15ステップ後に、 "10" の後に "1" が[[クヌースの矢印表記|10↑↑15]] 個以上連続して続く出力で停止)<ref>{{Cite web |title=BB(6, 2) > 10↑↑15 |url=https://www.sligocki.com//2022/06/21/bb-6-2-t15.html |website=sligocki |date=2022-06-21 |access-date=2024-07-11 |language=en |first=Shawn |last=Ligocki}}</ref>

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

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

例として、これまで発見された中で最も長く走る 3-状態 3-記号マシンは、停止するまでに 119,112,334,170,342,540 ステップ走行する<!--[http://www.cse.unr.edu/~al/BusyBeaver.html]-->。 また、6-状態 2-記号マシンに対し、各ステップ毎にテープ上の値を反転する機能を付加した場合、最も長く走るマシンは 6,147 個の 1 を 47,339,970 ステップで印字する。したがって、{{math|''S''<sub>RTM</sub>(6) ≧ 47,339,970 かつ Σ<sub>RTM</sub>(6) ≧ 6,147}} である。

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

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

これらの値を達成したチューリングマシンの実例は[http://www.drb.insel.de/~heiner/BB/ Heiner Marxenのサイト]か[http://www.logique.jussieu.fr/~michel/ha.html Pascal Michelのサイト]で見ることができる。これらのウェブサイトでは、他にもチューリングマシンに関する研究や正確な値についての証明などが紹介されている。

'''S(''n'',''m'') の値''':
:{| 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" | ≧ 10↑↑15
|-
! 3-記号
| align="right" | 38
| align="right" | ≧&nbsp;119,112,334,170,342,540
| align="right" | ≧ 1.0 × 10<sup>14072</sup>
| align="center" | ???
| align="center" | ???
|-
! 4-記号
| align="right" | ≧ 3,932,964
| align="right" | ≧ 5.2 × 10<sup>13036</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
|-
! 5-記号
| align="right" | ≧ 1.9 × 10<sup>704</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
| align="center" | ???
|-
! 6-記号
| align="right" | ≧ 2.4 × 10<sup>9866</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
| align="center" | ???
|}

'''Σ(''n'',''m'') の値''':
:{| 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" | ≧ 10↑↑15
|-
! 3-記号
| align="right" | 9
| align="right" | ≧ 374,676,383
| align="right" | ≧ 1.3 × 10<sup>7036</sup>
| align="center" | ???
| align="center" | ???
|-
! 4-記号
| align="right" | ≧ 2,050
| align="right" | ≧ 3.7 × 10<sup>6518</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
|-
! 5-記号
| align="right" | ≧ 1.7 × 10<sup>352</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
| align="center" | ???
|-
! 6-記号
| align="right" | ≧ 1.9 × 10<sup>4933</sup>
| align="center" | ???
| align="center" | ???
| align="center" | ???
| align="center" | ???
|}

==関連項目==
*[[コルモゴロフ複雑性]]

==脚注==
<references />

==参考文献==
<div class="references-small">
* Rado, Tibor (1962), ''On non-computable functions'', [[Bell System Technical Journal]], Vol. 41, No. 3 (May 1962), pp. 877-884. ラドーはこの中でビジービーバー問題を初めて定義し、それが計算不能であることと如何なる計算可能関数よりも急速に増大することを証明した。
* Lin, Shen and Rado, Tibor (1965), [http://portal.acm.org/citation.cfm?doid=321264.321270 ''Computer Studies of Turing Machine Problems''], [[Journal of the ACM]], Vol. 12, No. 2 (April 1965), pp. 196-212. リンはラドーの下で博士課程を学ぶ学生だった。この論文はリンの学位論文の一部として書かれた。リンは、すべての3-状態 2-記号チューリングマシンは、21ステップで停止しないなら、以後決して停止しないことを証明し、そこから Σ(3) = 6 かつ S(3) = 21 であることを示した。（ほとんどはコンピュータプログラムによって自動的に証明しているが、40 は人手で調べている）
* Brady, Allen H. (1983), [http://www.jstor.org/view/00255718/di970586/97p0337t/0 ''The determination of the value of Rado's noncomputable function Sigma(k) for four-state Turing machines''], [[Mathematics of Computation]], Vol. 40, No. 162 (April 1983), pp. 647-665. ブレイディは Σ(4) = 13 かつ S(4) = 107 であることを証明している。ブレイディは停止しない 3-状態 2-記号チューリングマシンについて2つの新たなカテゴリを定義した。「クリスマス・ツリー」と「カウンタ」である。彼はあるコンピュータプログラムを用いて、107ステップを越えて走行するマシンは、27個を除いてすべてがクリスマス・ツリーかカウンタの変種であることを示し、つまり停止しないことを証明した。残りの27個（"holdouts" と呼ばれる）については、ブレイディ自身の手作業によって停止しないことが証明された。
* Machlin, Rona and Stout, Quentin F. (1990), [http://www.eecs.umich.edu/~qstout/abs/busyb.html ''The complex behavior of simple machines''], [[Physica D]], No. 42 (June 1990), pp. 85-98.  マチリンとスタウトはビジービーバー問題を取り上げ、ビジービーバーを特定するための様々な技法を展開している（彼らはこれを 4-状態 2-記号チューリングマシンに適用し、それによってブレイディの証明を検証した）。彼らは 4-状態 2-記号 以下のマシンについて既知であるすべての S の値を用いて、[[チャイティンの定数|チャイティンの停止確率]](Ω) の変種の値を推定した。
* Marxen, Heiner and Buntrock, Jurgen (1990), [http://www.drb.insel.de/~heiner/BB/mabu90.html ''Attacking the Busy Beaver 5''], Bulletin of the EATCS, No 40 (February 1990), pp. 247-251. マルクセンとバントロックはΣ(5) の下限が 4098 かつ S(5) の下限が 47,176,870 であることを示し、彼らがマシンを見付けるために用いた手法を詳述しつつ、他の多くのマシンが停止しないことを証明した。
* Green, Milton W. (1964), ''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 [http://grail.cba.csuohio.edu/~somos/busy.html#dewd April 1985 p. 30].
** Dewdney, Alexander K. ''A computer trap for the busy beaver, the hardest working Turing machine'', Scientific American, 251 (2), 10-17, 1984.
* Chaitin, Gregory J. (1987), [http://www.umcs.maine.edu/~chaitin/bellcom.pdf ''Computing the Busy Beaver Function''], In T. M. Cover and B. Gopinath, ''Open Problems in Communication and Computation'', Springer, 1987, pp. 108-112.
* Brady, Allen H. (1995), ''The Busy Beaver Game and the Meaning of Life'', p 237-254, appearing in Herken, Rolf (ed)., ''The Universal Turing Machine: A Half-Century Survey'', 2nd edition (1995), Springer-Verlag, Wien New York. この中でブレイディは（4-状態について）この問題の歴史を紹介し「ビジービーバー・ゲーム」と呼んだ。彼は他のゲームについても言及している（例えば [[セル・オートマトン]]や[[ライフゲーム]]など). 特に興味深いのは247頁にある「二次元ビジービーバー・ゲーム」である。参考文献を19本挙げている。
* {{仮リンク|テイラー・ブース|en|Taylor Booth}}, ''Sequential Machines and Automata Theory'', Wiley, New York, 1967. Cf Chapter 9, Turing Machines. 難しい本で、電気系の専門職・技術職向けに書かれている。再帰や部分再帰を論じ、チューリングマシンや停止問題に言及する。ブースは脚注の中でビジービーバーをラドーの業績として紹介している。ブースはまたラドーのビジービーバー問題を第9章396頁の「宿題」3, 4, 5, 6 の中で定義している。この中で問題 3 は「すべての n について、ビジービーバーが解決不能であることを示せ」である。
</div>

==外部リンク==
* The page of [http://www.drb.insel.de/~heiner/BB/ Heiner Marxen], who, with Jurgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
* Pascal Michel's [http://www.logique.jussieu.fr/~michel/ha.html Historical survey] of busy beaver results which also contains best results and some analysis.
* The page of [http://eden.dei.uc.pt/~machado/research/bb/BB.html Penousal Machado's Genetic Beaver Project] uses Evolutionary Computation to find new candidates to the busy beaver Problem
* Definition of the class [http://skelet.ludost.net/bb/RTM.htm RTM] - Reversal Turing Machines, simple and strong subclass of the TMs.
* The "[http://www.cs.rpi.edu/~kelleo/busybeaver/ Millennium Attack]" at the Rensselaer RAIR Lab on the busy beaver Problem.
*Aaronson, Scott (1999), ''[http://www.scottaaronson.com/writings/bignumbers.html Who can name the biggest number?]''
* {{MathWorld |title=Busy Beaver |urlname=BusyBeaver}}
* ''[http://demonstrations.wolfram.com/BusyBeaver/ Busy Beaver]'' by Hector Zenil, [[Wolfram Demonstrations Project]].


{{Normdaten}}
{{DEFAULTSORT:ひしいひいはあ}}
[[Category:チューリングマシン]]
[[Category:計算可能性理論]]
[[Category:計算理論]]
[[Category:動物に関するメタファー]]
[[Category:数学に関する記事]]