忙しいビーバー

理論計算機科学において、ビジービーバーゲームは、与えられたサイズで（定義に応じて）可能な限り最大の出力を生成するか、または最長のステップ数で実行される終了プログラムを見つけることを目的とします。 ^[2]無限の出力を生成するか、無限の時間実行される無限ループプログラムは簡単に思いつくため、そのようなプログラムはゲームから除外されます。[ ^2]ゲームで使用されるプログラムは、従来のプログラミング言語ではなく、 n状態チューリングマシンです。 ^[2]これは、計算の最初の数学的モデルの1つです。^[3]

チューリングマシンは、無限のテープと、プログラムの「ソースコード」として機能する有限の状態セットで構成されています。最大の出力を生成することは、テープに最も多くの 1 を書き込むこと (最高スコアを達成することとも呼ばれます) と定義され、最も長い時間実行することは、停止するまでのステップ数が最も長いことと定義されます。^[4] n状態ビジービーバーゲームは、 n状態を持ち、最終的に停止するチューリングマシンのうち、最も長く実行されているか、最も高いスコアを獲得しているものを見つけることです。^[2]このようなマシンは、空のテープから開始し、テープには 0 と 1 のみが含まれていると想定されています (バイナリチューリングマシン)。^[2]このゲームの目的は、マシンが最終的に停止するようにしながら、最高のスコアまたは最長の実行時間を目指して、状態間の一連の遷移をプログラムすることです。

n番目のビジービーバー、BB- nまたは単に「ビジービーバー」は、n 状態のビジービーバーゲームに勝利するチューリングマシンです。[5] 定義に応じて、他のすべての可能な n 状態の競合チューリングマシンの中で、最高のスコアを獲得するか、最も長い時間実行されます。各定義による n状態^のビジービーバーの最高スコアまたは最長実行時間を決定する関数は、それぞれΣ(n)とS(n)です。^[4]

n番目のビジービーバーの実行時間やスコアを決定することは計算不可能です。^[4]実際、関数 Σ(n) と S(n) は両方とも、最終的にはどの計算可能関数よりも大きくなります。^{[4]これは、}計算可能性理論、停止問題、および複雑性理論に影響を与えます。^[6]この概念は、1962 年の論文「計算不可能な関数について」でTibor Radóによって初めて導入されました。 ^{[4]ビジービーバーゲームの最も興味深い側面の 1 つは、関数 Σ(n) と S(n) をすべての}nに対して計算できる場合、「このチューリングマシンは停止するかどうか」としてエンコードできるすべての数学的推測が解決されることです。^[5]例えば、27状態のチューリングマシンは、各数についてゴールドバッハの予想をチェックし、反例で停止することができます。このマシンがS(27)ステップ実行した後に停止しなかった場合、予想を解決しながら永遠に実行する必要があります。^[5]リーマン予想（744状態）やZF集合論の無矛盾性（745状態^{[7] [8]} ）を含む他の多くの問題も同様の形式で表現でき、最大で可算無限個のケースをチェックする必要があります。^[5]

ティボール・ラドの 1962 年の論文で導入された n 状態ビジービーバーゲーム (または BB-n ゲーム) には、チューリングマシンのクラスが含まれており、各メンバーは次の設計仕様を満たす必要があります。

• マシンにはn 個の「動作」状態と 1 個の停止状態があります。ここでn は正の整数であり、n 個の状態のうち 1 つが開始状態として区別されます。(通常、状態は 1、2、...、nでラベル付けされ、状態 1 が開始状態になります。または、 A、B、C、...でラベル付けされ、状態Aが開始状態になります。)
• このマシンは、単一の双方向無限（または無制限）テープを使用します。
• テープのアルファベットは {0, 1} で、0 は空白記号として機能します。
• マシンの遷移関数は2 つの入力を受け取ります。

1. 現在の非停止状態、
2. 現在のテープセル内のシンボル、

3 つの出力を生成します。

1. 現在のテープセルのシンボルを上書きするシンボル（上書きされるシンボルと同じシンボルの場合もあります）。
2. 移動する方向（左または右、つまり現在のセルの左または右のテープセルに移動する）および
3. 遷移する状態（Halt 状態の場合もあります）。

マシンを「実行」するには、開始状態から開始します。現在のテープ セルは、空白 (すべて 0) テープの任意のセルです。その後、Halt 状態 (ある場合) になるまで遷移関数を繰り返します。マシンが最終的に停止した場合、テープに最終的に残っている 1 の数は、マシンのスコアと呼ばれます。したがって、 n状態ビジー ビーバー (BB- n ) ゲームは、定義に応じて、可能な限り最大のスコアまたは実行時間を持つ n状態チューリング マシンを見つけるためのコンテストです。

1 状態のチューリング マシンのルールは次のようになります。

• 状態1で、現在のシンボルが0の場合、1を書き、右に1つ移動し、状態1に遷移します。
• 状態1では、現在のシンボルが1の場合、0を書き込み、右に1つ移動し、HALTに遷移します。

このチューリング マシンは右に移動し、通過するすべてのビットの値を入れ替えます。開始テープはすべて 0 なので、1 の連続が終わりなく続きます。このマシンは空のテープ上で永遠に実行されるため、忙しいビーバー コンテンダーにはなりません。

1962 年のオリジナルの論文で、ラドーはビジービーバーゲームに関連する 2 つの関数を定義しました。スコア関数 Σ(n) とシフト関数 S(n) です。^[4]どちらもチューリングマシンの状態をいくつか受け取り、ある基準でその状態数のチューリングマシンが達成可能な最大スコアを出力します。スコア関数 Σ(n) は、- 状態のチューリングマシンが停止する前に出力できる 1 の最大数を示します。一方、シフト関数 S(n) は、 - 状態のチューリングマシンが停止する前に実行できるシフト (または各ステップにシフトが含まれるため、ステップと同等) の最大数を示します。^[4]彼は、これらの関数はどちらも計算不可能であることを証明しました。なぜなら、どちらも計算可能な関数よりも速く成長するからです。^[4]関数 BB(n) は、これらの関数のいずれかとして定義されているため^{[引用が必要]} 、この記事では表記法は使用していません。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

チューリングマシンの性能を時間や最大個数以外の方法で測定することで、他の計算不可能な関数も定義できる。^[9]例えば: ^[9]

• この関数は、停止チューリングマシンが空のテープ上に書き込むことができる連続する1の最大数として定義されます。言い換えると、これはn状態のチューリングマシンがテープ上に書き込むことができる最大の単項数です。${\displaystyle {\text{num}}(n)}$
• この関数は、停止するチューリング マシンが停止する前に読み取る(つまり、訪問する) ことができるテープ スクエアの最大数として定義されます。これには開始スクエアが含まれますが、停止遷移後にマシンが到達するスクエア (停止遷移に移動方向が注釈されている場合) は含まれません。そのスクエアはマシンの動作に影響を与えないためです。これは、n状態チューリング マシンの最大の空間計算量です。${\displaystyle {\text{space}}(n)}$

これら4つの関数は、関係式 で表されます。^[9]また、3シンボルチューリングマシン、^[10]非決定性チューリングマシン、^[11]ラムダ計算（OEISのシーケンスA333479）、さらには任意のプログラミング言語など、さまざまなコンピューティングマシンでゲームを操作することで、さらに多くの関数を定義することができます。^[10]${\displaystyle {\text{num}}(n)\leq \Sigma (n)\leq {\text{space}}(n)\leq S(n)}$

スコア関数は、与えられた尺度で忙しいビーバーが達成できる最大スコアを定量化する。これは計算不可能な関数である。なぜなら、それはどんな計算可能関数よりも漸近的に速く増加するからである。 ^[12]

スコア関数は、空白のテープ上で開始された場合、上記のタイプのすべての停止2シンボルn状態チューリングマシンの中で、Σ( n )が達成可能な最大スコア（テープ上に最終的に残る1の最大数）となるように定義されます。 ${\displaystyle \Sigma :\mathbb {N} \to \mathbb {N} }$

Σ は明確に定義された関数であることは明らかです。つまり、すべてのnに対して、同型性を除いて上記のようなn状態のチューリング マシンは最大でも有限個存在し、したがって実行時間も最大でも有限個存在します。

スコアベースの定義によれば、σ ( M ) = Σ( n ) (つまり、最大スコアを達成する)となるn状態 2 シンボル チューリング マシンM は、ビジー ビーバーと呼ばれます。各nに対して、少なくとも 4( n − 1)!個のn状態ビジー ビーバーが存在します。(任意のn状態ビジー ビーバーについて、別のビジー ビーバーは停止遷移でシフト方向を変更するだけで得られ、3 つ目はすべてのシフト方向を一様に反転することで得られ、4 つ目はすべて入れ替えられたビジー ビーバーの停止方向を反転することで得られます。さらに、開始と停止を除くすべての状態を順列化すると、同じスコアを達成するマシンが生成されます。理論的には、停止状態に至る遷移の種類は複数ある可能性がありますが、実際には、目的の結果を生み出す状態遷移のシーケンスは 1 つしかないため、無駄が多くなります。)

ラドーの1962年の論文は、が任意の計算可能関数である場合、十分に大きいnに対してΣ( n ) > f ( n )であり、したがってΣは計算可能関数ではないことを証明した。^[4]${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

さらに、これは、任意のチューリングマシンがビジービーバーであるかどうかを一般的なアルゴリズムで決定できないことを意味します。(そのようなアルゴリズムは存在できません。なぜなら、その存在によって Σ を計算できるようになるためですが、これは不可能であることが証明されています。特に、そのようなアルゴリズムを使用して、次のように Σ を計算する別のアルゴリズムを構築できます。任意のnに対して、有限個のn状態 2 シンボルチューリングマシンのそれぞれを、 n状態のビジービーバーが見つかるまでテストします。次に、このビジービーバーマシンをシミュレートしてスコアを決定します。スコアは定義により Σ( n ) です。)

Σ( n ) は計算不可能な関数ですが、 nが小さい場合にはその値を得て正しいことを証明することができます。Σ(0) = 0、Σ(1) = 1、Σ(2) = 4 であることを示すのは難しくありません。また、徐々に難しくなりますが、Σ(3) = 6、Σ(4) = 13、Σ(5) = 4098 であることを示すことができます ( OEISのシーケンスA028444 ) 。n > 5の場合、Σ( n ) はまだ決定されていませんが、下限は確立されています (以下の既知の値のセクションを参照)。

コルモゴロフ複雑性の変種は次のように定義される: ^[13]数nの 複雑性は、最初は空白のテープ上のn 個の連続する 1の単一ブロックで停止する BB クラスのチューリングマシンに必要な最小の状態数である。対応するチャイティンの不完全性定理の変種は、自然数に対する与えられた公理系の文脈において、特定の数がkより大きい複雑性を持つことが証明できない数kが存在し、したがって Σ( k ) に対して特定の上限が証明できないことを述べている (後者は、n > Σ( k )が証明されれば「 nの複雑性はkより大きい」ことが証明されるためである)。引用文献で述べられているように、「通常の数学」の公理系では、これが当てはまる最小の値k は10⇈10よりはるかに小さい。したがって、通常の数学の文脈では、Σ(10⇈10) の値も上限も証明することはできません。 (ゲーデルの第一不完全性定理はこの結果によって示されます。通常の数学の公理系では、Σ(10⇈10) = nという形式の真だが証明不可能な文があり、 Σ(10⇈10) < nという形式の真だが証明不可能な文が無限に存在します。)

関数Σに加えて、ラド[1962]はチューリングマシンのもう一つの極端な関数である最大シフト関数Sを導入した。これは次のように定義される: ^[4]

• s ( M ) = 任意のM ∈ E _nに対して、 M が停止するまでのシフト数、
• S ( n ) = max{ s ( M ) | M ∈ E _n } = 停止するn状態の2シンボルチューリングマシンによって行われるシフトの最大数

通常のチューリング マシンでは、すべての遷移または「ステップ」(停止状態への遷移を含む) でシフトを実行する必要があるため、max-shifts 関数は同時に max-steps 関数でもあります。

ラドーは、 Σが計算不可能であるのと同じ理由でSが計算不可能であることを示した。つまり、 Sはどの計算可能関数よりも速く増加するということである。彼はこれを、各nについてS ( n )≥Σ( n )であることに注目するだけで証明した。各シフトはテープに0または1を書き込む可能性があるが、Σは1を書き込んだシフトのサブセット、つまりチューリングマシンが停止するまでに上書きされなかったシフトをカウントする。その結果、Sは少なくともΣと同じ速さで増加し、Σはどの計算可能関数よりも速く増加することがすでに証明されている。^[4]

Σ とSの間の次の関係は、Lin と Radó [ Computer Studies of Turing Machine Problems、1965] によって、Σ(3) = 6 および S(6)=21 を証明するために使用されました。与えられたnに対して、S ( n ) が既知であれば、すべてのn状態チューリングマシンは (原理的には) 最大S ( n ) ステップまで実行でき、その時点でまだ停止していないマシンは決して停止しません。その時点で、テープ上で最も多くの 1 で停止したマシン (つまり、忙しいビーバー) を観察することにより、そのテープから Σ( n )の値を取得します。 Lin と Radó がn = 3の場合に使用したアプローチは、 S (3) = 21と推測し(18 と推測して失敗した後)、本質的に異なる 3 状態マシン (82,944 台、2 ¹⁰ 3 ⁴に等しい) をすべて 21 ステップまでシミュレートするというものでした。彼らは、21 ステップ後にのみ停止したマシンを含む、停止したマシンが 26,073 台あることを発見しました。21 ステップ以内に停止しなかったマシンの動作を分析することで、それらのマシンのどれも停止することはなく、そのほとんどは特定のパターンに従うことを示すことに成功しました。これにより、S (3) = 21 という推測が証明され、Σ(3) = 6 であることが決定されました。これは、11 ステップから 14 ステップ後に停止したいくつかのマシンによって達成されました。^[14]

2016年、アダム・イェディディアとスコット・アーロンソンは、 ZFCでS( n ) が証明不可能となる最小のnに関する最初の（明示的な）上限を得ました。そのために彼らは、合理的な一貫性仮説（定常ラムゼー性）の下で、集合論の通常の公理（選択公理を伴うツェルメロ–フランケル集合論）に基づいて動作を証明できない7910状態^[15]のチューリングマシンを構築しました。^{[16] [17]}その後、ステファン・オリアは定常ラムゼー性への依存を排除​​してこれを1919状態に削減し、^{[18] [19]}その後748状態に削減しました。^[6] 2023年7月、リーベルはこれを745状態に削減しました。^{[7] [8]}

S ( n ) が計算可能関数であり、 EvalS が S ( n ) を評価する TM を表すものとします。n個の1を含むテープが与えられると、テープ上にS ( n ) 個の 1 を生成し、停止します。Clean が、テープ上に最初に書き込まれた 1 のシーケンスをクリーニングするチューリングマシンを表すものとします。 Double が、関数n + n を評価するチューリングマシンを表すものとします。n 個の1を含むテープが与えられると、テープ上に 2 n個の 1 を生成し、停止します。 Double | EvalS | Cleanという合成を作成し、このマシンの状態数をn _{0とします。} Create_n ₀が、最初は空のテープ上にn _{0 個の}1 を作成するチューリングマシンを表すものとします。このマシンは、 n ₀個の状態 (状態i は1 を書き込み、ヘッドを右に移動して状態i + 1 に切り替わり、状態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 をEva​​lΣに、Clean をIncrementに置き換える必要があります。これは、テープ上の最初の 0 を検索して 1 に置き換える単純な TM です。

S ( n )の計算不可能性は、空白テープ停止問題を参照することによっても立証できます。空白テープ停止問題は、任意のチューリング マシンが空のテープで起動したときに停止するかどうかを決定する問題です。空白テープ停止問題は標準の停止問題と同等であるため、これも計算不可能です。S ( n )が計算可能であれば、任意のチューリング マシンをn状態でS ( n ) ステップ実行するだけで、空白テープ停止問題を解決できます。それでも停止しない場合は、停止することはありません。したがって、空白テープ停止問題は計算不可能であるため、S ( n ) も同様に計算不可能であるはずです。

関数と は両方とも計算不可能です。^[9]これは、チューリングマシンが 1 を書き込むすべてのテープ スクエアは、 も訪問する必要があることに注目することで示されます。言い換えると、 です。 ^[9] 関数が計算不可能であることは、たとえば を証明することで示されます。これは、 n状態のスペース チャンピオンをシミュレートし、それを使用して少なくとも連続する 1 をテープに書き込む(3n+3)状態チューリングマシンを設計することで証明できます。^[9]${\displaystyle {\text{space}}(n)}$${\displaystyle {\text{num}}(n)}$${\displaystyle {\text{space}}(n)}$${\displaystyle \Sigma (n)\leq {\text{space}}(n)}$${\displaystyle {\text{num}}(n)}$${\displaystyle {\text{space}}(n)<{\text{num}}(3n+3)}$${\displaystyle {\text{space}}(n)}$

シフト関数の類似物は、プログラムをビット文字列で記述でき、プログラムのステップ数を数えることができる限り、どのプログラミング言語でも簡単に定義できます。^[10]たとえば、ビジービーバーゲームは、2次元テープ上のチューリングマシンを使用して2次元に一般化することも、同じ場所に留まることと左右に移動することが許可されているチューリングマシンに一般化することもできます。^[10]あるいは、さまざまな計算モデルの「ビジービーバー関数」をコルモゴロフ複雑度で定義できます。^[10]これは、 を となる最大の整数とすることで行われます。ここで、 はを出力するの最短プログラムの長さです。したがって、 で長さまたはそれ以下のプログラムが出力できる最大の整数です。^[10]${\displaystyle {BB}(n)}$${\displaystyle m}$${\displaystyle K_{L}(m)\leq n}$${\displaystyle K_{L}(m)}$${\displaystyle L}$${\displaystyle m}$${\displaystyle {BB}(n)}$${\displaystyle n}$${\displaystyle L}$

各ステップでテープの値を反転するという追加の特性を持つ、最も長く稼働している6状態、2シンボルのマシンは、6147 1秒後47 339 970ステップ。^[要出典]したがって、逆チューリングマシン（RTM）クラスの場合、^[20] S _RTM（6）≥47 339 970および Σ _RTM (6) ≥6147 。同様に、レジスタマシンの Σ 関数に相当するものを、与えられた数の命令に対して停止時に任意のレジスタに存在できる最大の数として定義することができます。^{[引用が必要]}

単純な一般化は、2つのシンボル（0と1）だけでなくm個のシンボルを持つチューリングマシンへの拡張である。 ^[10]たとえば、m = 3のシンボルを持つ3値チューリングマシンは、シンボル0、1、2を持つ。n状態とm個のシンボルを持つチューリングマシンへの一般化は、次の一般化されたビジービーバー関数を定義する。

1. Σ( n , m ):最初は空白のテープで起動し停止するまでにn状態、mシンボルのマシンが印刷できる非ゼロの最大数、 ^[要出典]および
2. S ( n , m ):最初は空白のテープ上で開始されたn状態、mシンボルのマシンが停止するまでに実行した最大ステップ数。 ^[10]

例えば、これまでに発見された最も長く稼働している3状態3シンボルマシンは、119 112 334 170 342 540歩で停止した。^{[21] [より良い情報源が必要]}

この問題は、すべての分岐にわたって最も多くの状態を持つシステム、または最も長いステップ数を持つ分岐を探すことで、非決定性チューリングマシンに拡張できます。 ^[11]特定の NDTM が停止するかどうかという問題は、依然として計算上は還元不可能であり、NDTM ビジービーバーを見つけるために必要な計算は、考慮する必要がある複数の分岐があるため、決定論的なケースよりも大幅に大きくなります。p個のケースまたはルールを持つ 2 状態、2 色のシステムの場合、右の表は、停止するまでの最大ステップ数と NDTM によって作成される一意の状態の最大数を示しています。

ビジービーバー関数 Σ(n) とS ( n ) は、かなり難しい数学ゲームを提起するだけでなく、純粋数学の問題を解くまったく新しいアプローチを提供します。数学の多くの未解決問題は、十分に大きなnに対してS ( n )の値が与えられれば、理論的には体系的な方法で解決できますが、実際にはそうではありません。^{[5] [22]理論的に言えば、 S(n) の値は、} n状態以下のチューリングマシンによって無限時間でチェックできるすべての数学的推測の答えをエンコードします。^[6]

任意の予想:可算な数のケースの中から反例によって反証できる予想(例:ゴールドバッハの予想) を考えてみましょう。この予想を増加する値について順次テストするコンピュータ プログラムを作成します。ゴールドバッハの予想の場合、4 以上のすべての偶数を順に検討し、それが 2 つの素数の和であるかどうかをテストします。このプログラムがn状態のチューリング マシンでシミュレートされるとします。反例 (この例では 2 つの素数の和ではない 4 以上の偶数) が見つかった場合、プログラムは停止し、そのことを示します。ただし、予想が正しい場合、プログラムは決して停止しません。(このプログラムは反例が見つかった場合のみ停止します。) ^[6]${\displaystyle \Pi _{1}^{0}}$

さて、このプログラムはn状態のチューリングマシンでシミュレートされるので、 S ( n )がわかれば、マシンをそのステップ数だけ実行するだけで、マシンが停止するかどうかを (有限の時間内に) 判断できます。そして、S ( n ) ステップ実行後もマシンが停止しない場合は、マシンが停止することは決してなく、したがって、与えられた予想に対する反例 (つまり、2 つの素数の和ではない偶数) がないことがわかります。これは、予想が正しいことを証明します。^{[6]したがって、} S ( n )の特定の値 (または上限) は、理論的には、数学の多くの未解決問題を体系的に解決するために使用できます。^[6]

しかし、忙しいビーバー問題に関する現在の結果は、次の2つの理由からこれは実用的ではないことを示唆している。^{[引用が必要]}

• ビジービーバー関数（および最大シフト関数）の値を証明するのは非常に困難です。S ( n ) の既知の正確な値はすべて、すべてのn状態のチューリングマシンを列挙し、それぞれが停止するかどうかを証明することによって証明されました。実際に役立つためには、S (n) をそれほど直接的ではない方法で計算する必要があります。 ^{[引用が必要]}
• S(n) やその他のビジービーバー関数の値は、非常に急速に大きくなります。S(5) の値は 4700 万程度ですが、S(6) の値は 10⇈15 を超えており、これは15 個の 10 を積み重ねた場合に相当します。^{[10] [より良いソースが必要]この数は 10⇈14 桁であり、計算に使用するのは無理があります。S(27) の値は、}ゴールドバッハ予想の現在のプログラムを実行して決定的な答えを出すために必要なステップ数ですが、理解できないほど巨大であり、観測可能な宇宙で書き留めることはおろか、マシンを実行することすら不可能です。^[5]${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$

S(n) のもう 1 つの特性は、算術的に健全で計算可能に公理化された理論で関数の値のすべてを証明できるものはないということです。具体的には、計算可能で算術的に健全な理論 が与えられた場合、すべての に対して、 の形式のステートメントは で証明できないような数が存在します。^[6]これは、各理論について、証明できる S(n) の特定の最大値が存在することを意味します。これは、そのような のすべてについて、状態を持つチューリングマシンをにおけるすべての可能な証明を列挙するように設計できるため当てはまります。^[6]理論に矛盾がある場合、すべての誤ったステートメントは証明可能であり、チューリングマシンには、たとえば の証明が見つかった場合のみ停止するという条件を与えることができます。^[6]の値を証明する理論は、それ自体の一貫性を証明し、ゲーデルの第二不完全性定理に違反します。^[6]これを使って、様々な理論をスケール上に置くことができます。例えば、ZFCの様々な大きな基数公理です。各理論にその番号が割り当てられている場合、 のより大きな値を持つ理論は、それより低い理論の一貫性を証明し、そのような理論をすべて可算無限スケール上に置きます。^[6]${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle n\geq n_{T}}$${\displaystyle S(n)=k}$${\displaystyle T}$${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle T}$${\displaystyle 0=1}$${\displaystyle S(n_{T})}$${\displaystyle T}$${\displaystyle n_{T}}$${\displaystyle n_{T}}$

• ZFCが矛盾する場合にのみ 停止する745状態のバイナリチューリングマシンが構築されました。^{[7] [8]}

• リーマン予想が偽である場合にのみ停止する744状態のチューリングマシンが構築されました。^{[18] [5]}

• 2016年には、ゴールドバッハの予想が偽である場合にのみ停止する43状態のチューリングマシンが構築されました。これはさらに27状態のマシンに縮小され、^{[18] [5] 、2024年にこの構成は}Lean 4定理証明言語で正式に証明され、検証されました。 ^[23]

• 1979年にポール・エルデシュが提唱した次の予想が偽である場合にのみ停止する15状態のチューリングマシンが構築されました。n > 8のすべてにおいて、²ⁿの3進数表現には少なくとも1つの数字2が含まれます。^{[24] [25]}

ビジービーバーチューリングマシンの計算の普遍性と動的動作との関係を調査し、ビジービーバーマシンは複雑な特性、すなわち（1）サイズ制約内での最大の計算複雑性、（2）停止する前に非自明な計算を実行する能力、（3）これらのマシンを見つけて証明することの難しさ、を示すことから、チューリングの^普遍性の自然な候補であるという仮説が2012年に提案されました[26]。これらの特徴は、ビジービーバーマシンが普遍性に必要な複雑さを備えていることを示唆しています。

1964年、ミルトン・グリーンはビジービーバー関数の1秒カウント変種の下限値を開発し、1964年IEEEスイッチング回路理論と論理設計シンポジウムの議事録で発表した。ハイナー・マルクセンとユルゲン・バントロックはこれを「自明ではない（原始再帰的ではない）下限値」と表現した。^{[27]この下限値は計算できるが、} nに関して単一の式で表すには複雑すぎる。^[28]これは、あるnに対する下限値をそれぞれ示すチューリングマシンのセットで行われた。^[28] n =8のとき、この方法は次の式を与える。

${\displaystyle \Sigma (8)\geq 3\times (7\times 3^{92}-1)/2\approx 8.248\times 10^{44}}$。

対照的に、 の現在（2024年時点）の最良の下限は であり、各 はクヌースの上矢印表記である。^[10]これは、 に等しい15個の10の累乗連鎖を表す。 の値はおそらくそれよりさらに大きい。 ${\displaystyle \Sigma (6)}$${\displaystyle 10\uparrow \uparrow 15}$${\displaystyle \uparrow }$${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$${\displaystyle 10^{10\uparrow \uparrow 14}}$${\displaystyle \Sigma (8)}$

具体的には、下限は一連の再帰チューリングマシンで示され、各マシンは、入力テープに繰り返し適用する2つの追加状態を持つ小さなマシンで構成されていました。[ ^28] 1を含むテープ上のN状態ビジービーバー競合マシンの値を と定義すると（各マシンの最終的な出力は 上の値です。空のテープには1が0個あるため）、再帰関係は次のようになります。^[28 ] ${\displaystyle m}$${\displaystyle B_{N}(m)}$${\displaystyle m=0}$

${\displaystyle B_{N}(0)=1}$

${\displaystyle B_{1}(m)=m+1}$

${\displaystyle B_{N}(m)=1+B_{N-2}(1+B_{N}(m-1))}$

これにより、N 番目のマシンによって与えられた下限を計算するための、奇数と偶数の 2 つの式が得られます。 ${\displaystyle G(N)}$

${\displaystyle G(N)=B_{N-2}(B_{N-2}(1))}$奇数Nの場合

${\displaystyle G(N)=1+B_{N-3}(1+B_{N-3}(1))}$Nが偶数の場合

下限BB(N)はアッカーマン関数とも関連しており、次のように表すことができます。^[29]

${\displaystyle A(n,n)>G(4N+3)>A(4,2N+1)}$

自明なことに、S(n) ≥ Σ(n)である。なぜなら、Σ(n)個の1を書き込むマシンは、少なくともΣ(n)ステップを踏む必要があるからである。^[29] 1の数Σ(n)に応じて、S(n)の時間にいくつかの上限を与えることが可能である。

• ${\displaystyle S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}}$   （ラド^[29]）
• ${\displaystyle S(n)\leq \Sigma (9n)}$   （ブロ^[29]）
• ${\displaystyle S(n)\leq (2n-1)\times \Sigma (3n+3)}$   （ユルストロムとズウィック^[29]）

num(n)をn状態チューリングマシンが任意の位置ではなく連続して出力できる1の最大数（出力できる最大の単進数）と定義すると、次のことが示されます。^[29]

${\displaystyle {\text{num}}(n)<\Sigma (n)}$

${\displaystyle S(n)<{\text{num}}(n+o(n))}$

${\displaystyle S(n)<{\text{num}}(3n+6)}$   (Ben-Amram ら、1996 ^[9] )

ベン・アムラムとピーターセン（2002）もS(n)の漸近的に改善された境界を与えている。定数cが存在し、すべてのn ≥ 2に対して次のようになる：^[29]

${\displaystyle S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).}$

次の表は、 S ( n )、Σ( n )、および他のいくつかのビジービーバー関数の正確な値と既知の下限を示しています。この表では、2 シンボルのチューリングマシンが使用されています。「?」としてリストされているエントリは、少なくとも左側の他のエントリと同じ大きさです (すべての n ステートマシンは (n+1) ステートマシンでもあるため)。また、それらの上にあるエントリより大きくなりません (S(n) ≥ space(n) ≥ Σ(n) ≥ num(n) であるため)。したがって、space(n) ≥ Σ(n) かつ Σ(6) > 10⇈15 であるため、space(6) は 10⇈15 より大きいことがわかっています。47 176 870は空間(5)の上限である。なぜならS(5) =47 176 870 ( ^[3] ) かつS(n) ≥ space(n)。4098はnum(5)の上限である。なぜならΣ(5) = 4098 ( ^[29] ) かつΣ(n) ≥ num(n)だからである。「?」としてリストされている最後のエントリはnum(6)である。なぜならΣ(6) > 10⇈15であるが、Σ(n) ≥ num(n)だからである。

5状態のビジービーバーは1989年にハイナー・マルクセンとユルゲン・バントロックによって発見されましたが、2024年にCoqによる証明を使用して、勝利した5番目のビジービーバー（BB(5)と表記）であることが証明されました。^{[31] [32]}

これらは、Σ(1)とS (1)、Σ(2)とS (2)、Σ(3)(ただしS (3)は生成しない)、Σ(4)とS(4 )、Σ(5)とS( 5)、およびΣ(6)とS (6)の最もよく知られている下限値を生成するチューリングマシンの規則の表です。

表では、列は現在の状態を表し、行はテープから読み取られた現在のシンボルを表します。各表エントリは 3 文字の文字列で、テープに書き込むシンボル、移動する方向、および新しい状態 (この順序) を示します。停止状態はHとして表示されます。

各マシンは、すべて 0 を含む無限のテープを持つ 状態Aから開始します。したがって、テープから読み取られる最初のシンボルは 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」)。

これは6個の1を出す非等価なマシンのうちの1つである。これまでのマシンとは異なり、このマシンはΣに対しては忙しいが、Sに対しては忙しくない。（S（3）=21であり、マシンは5個の1しか出さない。^[14]）

結果: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 ステップ、合計 13 個の「1」)

結果: 47,176,870 ステップに 4098 個の「1」と 8191 個の「0」が混在します。

右の図では、このソリューションがセルオートマトンの一部の進化と質的に似ていることに注目してください。

結果: 1 0 1 1 1 ... 1 1 1 (「10」の後に 10↑↑15 以上の連続した「1」が 10↑↑15 ステップ以上続きます。ここで、10↑↑15=10 ^{10 . . 10}で、15 個の 10 の指数タワーです)。

次の表では、各ビジービーバーのルール (Σ を最大化する) が視覚的に表されており、オレンジ色の四角はテープ上の「1」に対応し、白は「0」に対応しています。頭の位置は黒い卵形で示され、頭の向きは状態を表します。個々のテープは水平に配置され、時間は上から下に向かって進行します。停止状態は、1 つの状態をそれ自体にマッピングするルール (頭は動きません) で表されます。

• ラヨの番号
• ターマイト

• Heiner Marxen のページ。彼は Jürgen Buntrock とともに、5 状態および 6 状態のチューリング マシンに関する上記の記録を発見しました。
• Pascal Michel による忙しいビーバーの結果の歴史的調査。これには最良の結果といくつかの分析も含まれています。
• RTM クラスの定義 - 逆チューリング マシン、TM のシンプルで強力なサブクラス。
• レンセラー RAIR 研究所の「忙しいビーバー問題: 新千年紀の攻撃」(アーカイブ)。この取り組みにより、いくつかの新しい記録が発見され、4 重形式化のいくつかの値が確立されました。
• Skelet (Georgi Georgiev) の非正規マシン リストに基づいて、5 状態、2 シンボルのビジー ビーバー問題を解決するための Daniel Briggs の Web サイト アーカイブおよびフォーラム。
• Ligocki, Shawn (2021-07-17). 「忙しいビーバーのコラッツのような行動」. sligocki . 2022-07-12閲覧。
• アーロンソン、スコット (1999) 「より大きな数字を挙げられるのは誰か?」
• Weisstein、Eric W.「Busy Beaver」。MathWorld。
• 忙しいビーバーのチューリングマシン - Computerphile、Youtube
• パスカル・ミシェル。ビジービーバー競争：歴史的調査。70 ページ。2017 年。<hal-00396880v5>