Loading article…
理論計算機科学において、ビジービーバーゲームは、与えられたサイズの終了するプログラムを見つけることを目的としており、そのプログラムは（定義に応じて）可能な限り最大の出力を生成するか、または最長のステップ数で実行されるかのいずれかである。 [ 2 ]無限にループして無限の出力を生成したり、無限に実行されたりするプログラムは容易に考えられるため、そのようなプログラムはゲームから除外される。[ 2 ]このゲームで使用されるプログラムは、従来のプログラミング言語ではなく、n状態チューリングマシンである。[ 2 ]これは、計算の最初の数学的モデルの1つである。[ 3 ]
チューリングマシンは無限のテープと、プログラムの「ソースコード」として機能する有限個の状態から構成されます。最も多くの出力を生成することは、テープに最も多くの 1 を書き込むこと、つまり最高得点を達成することと定義され、最も長い実行時間は、停止するまでに最も多くのステップを要したと定義されます。[ 4 ] n状態ビジービーバーゲームは、n 個の状態を持ち、最終的に停止する、最も長く実行されるか、最も高いスコアを獲得するチューリングマシンを見つけることから成ります。[ 2 ]このようなマシンは空のテープから開始すると想定され、テープにはゼロと 1 のみが含まれていると想定されます (バイナリチューリングマシン)。[ 2 ]ゲームの目的は、マシンが最終的に停止することを保証しながら、最高得点または最長実行時間を目指して状態間の遷移のセットをプログラムすることです。
n番目のビジービーバーの実行時間やスコアを決定することは計算不可能である。[ 4 ]実際、関数 Σ(n) と S(n) はどちらも最終的にはどの計算可能な関数よりも大きくなる。[ 4 ]これは計算可能性理論、停止問題、複雑性理論に影響を与える。[ 5 ]ビジービーバーの概念は、ティボール・ラドが1962 年の論文「計算不可能な関数について」で初めて導入した。[ 4 ]
ビジービーバーゲームの示唆するところは、すべてのnに対して関数 Σ(n) と S(n) を計算できる場合、停止問題に還元できるすべての数学的予想が解決されるということである。たとえば、「 ⟨このチューリングマシン⟩は停止するか」という形式に還元できる。[ 6 ]例えば、各数値に対してゴールドバッハ予想をチェックし、反例で停止する27 状態のチューリングマシンがある。このマシンが S(27) ステップ実行後に停止しなかった場合、永遠に実行されなければならず、予想が解決される。 [ 6 ] [ 7 ]リーマン予想(744 状態) やZF 集合論の無矛盾性(745 状態[ 8 ] [ 9 ] )など、他の多くの問題も同様の形式で表現でき、チェックする必要があるケースは可算無限個までである。[ 6 ]
ティボール・ラドが1962年の論文で発表したn状態ビジービーバーゲーム（またはBB- nゲーム）は、チューリングマシンの一種であり、その各メンバーは以下の設計仕様を満たす必要がある。
マシンの「実行」は、開始状態から開始し、現在のテープセルが空白（すべて0）テープの任意のセルである状態で、停止状態に入るまで（もしあれば）遷移関数を繰り返すことから成ります。マシンが最終的に停止する場合に限り、テープ上に最終的に残った1の数がマシンのスコアと呼ばれます。n番目のビジービーバー、BB- n 、または単に「ビジービーバー」は、 n状態のビジービーバーゲームに勝つチューリングマシンです。 [ 6 ]定義に応じて、他のすべての可能なn状態の競合チューリングマシンの中で、最高のスコア（Σ(n) [ 4 ]で表される）を獲得するか、最長の実行時間（S(n) ）を達成します。
1状態チューリングマシンのルールは次のようになるかもしれない。
このチューリングマシンは右方向に移動しながら、通過するすべてのビットの値を入れ替えます。開始テープはすべて0なので、無限に1の列が生成されます。このマシンは空のテープ上で永遠に動作し続けるため、ビジービーバーのような強力なマシンにはなり得ません。
ラドーは1962年の原著論文で、ビジービーバーゲームに関連する2つの関数、スコア関数Σ(n)とシフト関数S(n)を定義した。[ 4 ]どちらもチューリングマシンの状態数を取る。そして、その状態数を持つチューリングマシンが何らかの尺度で達成できる最大スコアを出力します。スコア関数 Σ(n) は、1 の最大数とn 状態のチューリングマシンは停止する前に n を出力できますが、シフト関数 S(n) は、チューリングマシンは停止する前に、状態 を経ることができます。[ 4 ]彼は、これらの関数はどちらも計算可能関数よりも速く増加するため、どちらも計算不可能であることを証明しました。 [ 4 ]関数 BB(n) はこれらの関数のいずれかとして定義されているため、この記事ではその表記は使用されていません。
時間や最大1数以外の方法でチューリングマシンの性能を測定することに基づいて、他にも多くの計算不可能な関数を定義することもできます。[ 10 ]例えば：[ 10 ]
これら4つの機能は、以下の関係にある。[ 10 ] 3 記号チューリング マシン[ 11 ]非決定性チューリング マシン[ 12 ]ラムダ計算( OEISのシーケンスA333479 )や任意のプログラミング言語[ 11 ]など、さまざまな計算機上でゲームを実行することによって、さらに多くの機能を定義することもできます。
スコア関数は、特定の尺度において、働き者のビーバーが達成できる最大スコアを定量化します。これは、漸近的に計算可能な関数よりも速く増加するため、計算不可能な関数です。 [ 13 ]
スコア関数、 :\mathbb {N} \to \mathbb {N} } は次のように定義されます。は、すべての停止2シンボルの中で達成可能な最大スコア（最終的にテープに残る1の最大数）です。-上記タイプのチューリングマシンを、空のテープで起動した場合。
明らかにこれは明確に定義された関数である。任意のnに対して、同型を除いて、上記のようなn状態チューリングマシンは最大で有限個しか存在せず、したがって実行時間も最大で有限個しか存在しない。[ 4 ] p. 880
スコアに基づく定義によれば、σ ( M ) = Σ( n )となる（すなわち、最大スコアを達成する）n状態2記号チューリングマシンMは、ビジービーバーと呼ばれる。各nに対して、少なくとも4( n - 1)!個のn状態ビジービーバーが存在する。（任意のn状態ビジービーバーが与えられた場合、停止遷移におけるシフト方向を変更するだけで別のビジービーバーが得られ、すべてのシフト方向を均一に反転させることで3つ目のビジービーバーが得られ、さらに、すべてのシフト方向を反転させたビジービーバーの停止方向を反転させることで4つ目のビジービーバーが得られる。さらに、開始状態と停止状態を除くすべての状態の順列によって、同じスコアを達成するマシンが生成される。理論的には、停止状態に至る遷移の種類は複数存在する可能性があるが、実際には、目的の結果を生み出す状態遷移のシーケンスは1つしかないため、無駄となる。）
ラドの1962年の論文は、もしが任意の計算可能な関数である場合、十分大きなすべてのnに対してΣ( n ) > f ( n ) となり、したがって Σ は計算可能な関数ではない。[ 4 ]
さらに、これは任意のチューリングマシンがビジービーバーであるかどうかを一般的なアルゴリズムで判定することは不可能であることを意味する。（そのようなアルゴリズムは存在し得ない。なぜなら、そのようなアルゴリズムが存在するとΣを計算できてしまうが、それは不可能であることが証明されているからである。特に、そのようなアルゴリズムは、次のようにΣを計算する別のアルゴリズムを構築するために使用できる。任意のnに対して、有限個のn状態2シンボルチューリングマシンをそれぞれテストし、 n状態のビジービーバーが見つかるまで続ける。そして、このビジービーバーマシンをシミュレートしてスコアを決定する。このスコアは定義によりΣ( n )である。）
Σ( n ) は計算不可能な関数ですが、 nが小さい場合、その値を取得して正しいことを証明できる場合があります。Σ(0) = 0、Σ(1) = 1、Σ(2) = 4 を示すのは難しくなく、難易度は上がりますが、Σ(3) = 6、Σ(4) = 13、Σ(5) = 4098 ( OEISのシーケンスA028444 )を示すことができます。n > 5の場合、 Σ( n ) はまだ決定されていませんが、下限値は確立されています (下記の「既知の値」のセクションを参照)。
コルモゴロフ複雑性の変種は次のように定義されます。[ 14 ]数nの 複雑性とは、最初に空白のテープ上でn個の連続する 1の単一ブロックで停止する BB クラスのチューリング マシンに必要な最小の状態数です。チャイティンの不完全性定理の対応する変種は、自然数の与えられた公理系の文脈において、特定の数がkより大きい複雑性を持つことが証明できないような数kが存在し、したがって Σ( k ) の特定の上限を証明することはできないと述べています (後者は、 n > Σ( k )が証明された場合に「 nの複雑性はkより大きい」が証明されるためです)。引用文献で述べられているように、「通常の数学」の任意の公理系では、これが真となる最小値kは10⇈10よりはるかに小さいです。したがって、通常の数学の文脈では、Σ(10⇈10) の値も上限も証明することはできません。（ゲーデルの第一不完全性定理はこの結果によって例示されます。通常の数学の公理系には、Σ(10⇈10) = nという形式の真であるが証明不可能な文が存在し、 Σ(10⇈10) < nという形式の真であるが証明不可能な文は無限に存在します。）
関数 Σ に加えて、Radó [1962] はチューリングマシン用のもう 1 つの極値関数、最大シフト関数Sを導入しました。これは次のように定義されます。[ 4 ]
通常のチューリングマシンでは、すべての遷移または「ステップ」（停止状態への遷移を含む）においてシフトが必要となるため、最大シフト関数は同時に最大ステップ関数でもある。
ラドーは、Sが計算不可能である理由は Σ が計算不可能である理由と同じであることを示した。つまり、 S はどの計算可能な関数よりも速く増加するからである。彼は、各nに対してS ( n ) ≥ Σ( n ) であることに注目するだけでこれを証明した。各シフトはテープに 0 または 1 を書き込む可能性があるが、Σ は 1 を書き込んだシフトのサブセット、つまりチューリング マシンが停止するまでに上書きされなかったシフトをカウントする。したがって、Sは少なくとも Σ と同じ速さで増加し、Σ はすでにどの計算可能な関数よりも速く増加することが証明されていた。[ 4 ]
Lin & Radó ( Computer Studies of Turing Machine Problems、1965) は、Σ(3) = 6 および S(3) = 21 を証明するために、 Σ とSの間の次の関係を使用しました。与えられたnに対して、S ( n ) が既知であれば、すべてのn状態チューリングマシンは (原理的に) S ( n ) ステップまで実行でき、この時点でまだ停止していないマシンは停止しません。その時点で、テープ上に最も多くの 1 で停止したマシン (つまり、ビジービーバー) を観察することで、テープから Σ(n) の値を取得できます。n = 3の場合に Lin & Radó が使用したアプローチは、S (3) = 21と予想し(18 と予想して失敗した後)、次に、本質的に異なるすべての 3 状態マシン (82,944 台のマシン、2 × 10³ × 4に相当) を最大 21 ステップまでシミュレートすることでした。彼らは停止した26,073台のマシンを発見したが、その中には21ステップ後にようやく停止したマシンも含まれていた。21ステップ以内に停止しなかったマシンの挙動を分析することで、それらのマシンはどれも停止せず、ほとんどが一定のパターンに従っていることを示すことに成功した。これにより、S (3) = 21という予想が証明され、また、11～14ステップ後に停止した複数のマシンで達成されたΣ(3) = 6も判明した。[ 15 ]
2016 年、アダム・イェディディアとスコット・アーロンソンは、ZFCでS( n ) が証明不可能となる最小nの最初の (明示的な) 上限を得ました。そのために、彼らは、妥当な一貫性仮説 (定常ラムゼー特性、任意に大きな微妙基数の存在と同等) の下で、通常の集合論の公理 (選択公理を持つツェルメロ・フレンケル集合論)に基づいて動作を証明できない 7910 状態[ 16 ]のチューリング マシンを構築しました。[ 17 ] [ 18 ] [ 19 ]その後、ステファン・オリアーは、定常ラムゼー特性への依存を排除して、それを 1919 状態に削減し[ 20 ] [ 21 ]、さらに 748 状態に削減しました。[ 5 ] 2023 年 7 月、リーベルはそれを 745 状態に削減しました。[ 8 ] [ 9 ]さらなる改善については、BB Challenge の Web サイトに掲載されています。
S ( n ) を計算可能な関数とし、 EvalS をS ( n )を評価するチューリングマシンとします。n 個の1が入ったテープが与えられると、テープ上にS ( n ) 個の 1 を生成し、停止します。Cleanを、テープに最初に書き込まれた 1 のシーケンスを消去するチューリングマシンとします。Doubleを、関数n + nを評価するチューリングマシンとします。n 個の1が入ったテープが与えられると、テープ上に2n 個の1 を生成し、停止します。Double | EvalS | Clean という合成を作成し、n0をこのマシンの状態数とします。Create_n0 を、最初に空白のテープ上にn0個の1を作成するチューリングマシンとします。このマシンは、 n0個の状態を持つように自明に構築できます(状態iは 1を書き込み、ヘッドを右に移動して状態i + 1 に切り替わりますが、状態n0は停止します)。Nをn0 + n0の和とします。
BadS を、Create_n 0 | Double | EvalS | Cleanという構成とします。このマシンにはN個の状態があることに注意してください。最初は空のテープから始めて、まずn 0個の 1 のシーケンスを作成し、次にそれを倍にして、 N個の 1 のシーケンスを生成します。次に、EvalS はテープ上に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 ) も同様に計算不能でなければなりません。
両方そして関数は計算不可能である。[ 10 ]これは、チューリングマシンが 1 を書き込むテープマスはすべて、次のマスも訪問しなければならないことに注目すると、[ 10 ] 関数は、例えば、次のことを証明することによって計算不可能であることが示される。これは、 n状態空間チャンピオンをシミュレートする(3n+3)状態チューリングマシンを設計し、それを使用して少なくともテープに隣接するもの。[ 10 ]
シフト関数の類似物は、プログラムをビット列で記述でき、プログラムのステップ数を数えることができる限り、どのプログラミング言語でも簡単に定義できます。[ 11 ]例えば、ビジービーバーゲームは、2次元テープ上のチューリングマシンを使用した2次元への一般化、または左右への移動だけでなく同じ場所に留まることも許されるチューリングマシンへの一般化も可能です。[ 11 ]あるいは、多様な計算モデルに対する「ビジービーバー関数」をコルモゴロフ複雑度で定義することもできます。[ 11 ]これは、次の式を用いることで実現できます。最大の整数となるそのため、 どこは、最短プログラムの長さです。出力:これにより、長さが最大の整数プログラムまたはそれ以下で出力できます[ 11 ]
各ステップでテープ値を反転させるという追加特性を持つ、最も長く稼働している6状態2シンボルマシンは、6147秒後47,339,970ステップ。したがって、反転チューリングマシン（RTM）クラスの場合、[ 22 ] S RTM（6）≥47 339 970および Σ RTM (6) ≥6147 。同様に、レジスタマシンの Σ 関数の類似物を、与えられた命令数に対して停止時に任意のレジスタに存在することができる最大の数として定義することもできます。[ 23 ]
単純な一般化としては、2つ（0と1）ではなくm個の記号を持つチューリングマシンへの拡張があります。 [ 11 ]例えば、m = 3個の記号を持つ3値チューリングマシンは、0、1、2の記号を持ちます。n個の状態とm個の記号を持つチューリングマシンへの一般化は、次の一般化されたビジービーバー関数を定義します。
例えば、これまでに発見された最長稼働の3状態3シンボルマシンは停止するまでに119 112 334 170 342 540歩。[ 24 ] [ 25 ]
この問題は、すべての分岐にわたって最も多くの状態を持つシステム、または最も長いステップ数を持つ分岐を探すことで、非決定性チューリングマシンに拡張できます。 [ 12 ]特定のNDTMが停止するかどうかという問題は、依然として計算的に還元不可能であり、考慮すべき複数の分岐があるため、NDTMのビジービーバーを見つけるために必要な計算は、決定性の場合よりもかなり大きくなります。p個のケースまたはルールを持つ2状態2色システムの場合、右の表は、停止するまでの最大ステップ数と、NDTMによって生成される一意の状態の最大数を示します。
かなり難しい数学ゲームを提示することに加えて、忙しいビーバー関数 Σ(n) とS ( n ) は、純粋数学の問題を解決するためのまったく新しいアプローチを提供します。数学における多くの未解決問題は、理論的には、十分に大きなnに対するS ( n )の値が与えられれば、体系的に解決できますが、実際には解決できません。[ 6 ] [ 26 ]理論的には、S(n) の値は、 n以下の状態を持つチューリングマシンによって無限時間でチェックできるすべての数学的予想に対する答えを符号化しています。[ 5 ]
どれでも検討してください予想：可算個のケースの中から反例によって反証できるあらゆる予想（例：ゴールドバッハ予想）。増加する値に対してこの予想を順次テストするコンピュータ プログラムを作成します。ゴールドバッハ予想の場合、4 以上のすべての偶数を順次検討し、それが 2 つの素数の和であるかどうかをテストします。このプログラムがn状態チューリング マシンでシミュレートされるとします。反例（この例では 2 つの素数の和ではない 4 以上の偶数）が見つかった場合、プログラムは停止し、その旨を示します。ただし、予想が正しい場合、このプログラムは決して停止しません。（このプログラムは反例が見つかった場合にのみ停止します。）[ 5 ]
さて、このプログラムはn状態チューリングマシンによってシミュレートされるため、 S ( n )が分かっていれば、マシンをそのステップ数だけ実行するだけで、(有限時間内に) 停止するかどうかを判断できます。そして、S ( n ) ステップ後にマシンが停止しない場合、マシンは決して停止しないことがわかり、したがって、与えられた予想に対する反例はありません (つまり、2 つの素数の和ではない偶数は存在しません)。これにより、予想が正しいことが証明されます。[ 5 ]したがって、理論的には、 S ( n )の特定の値 (または上限)を使用して、数学における多くの未解決問題を体系的に解決することができます。[ 5 ]
しかし、ビジービーバー問題に関する現在の研究結果は、以下の2つの理由から、これは実用的ではないことを示唆している。
S(n)のもう一つの特性は、算術的に健全で計算可能な公理化された理論では、この関数のすべての値を証明できないということである。具体的には、計算可能で算術的に健全な理論が与えられた場合、数がありますすべての、以下の形式の声明はありません証明できる[ 5 ]これは、各理論には証明できるS(n)の特定の最大値が存在することを意味する。これは、そのようなすべての理論に対して、チューリングマシン状態は、考えられるすべての証明を列挙するように設計できます。[ 5 ]理論が矛盾している場合、すべての偽の命題は証明可能であり、チューリングマシンは、たとえば、次の命題の証明を見つけた場合に限り停止するという条件を与えることができます。[ 5 ]価値を証明する理論これは、ゲーデルの第二不完全性定理に違反して、自身の無矛盾性を証明している。[ 5 ]これは、さまざまな理論を尺度上に配置するために使用できる。たとえば、ZFCのさまざまな大きな基数公理の場合、各理論が番号として割り当てられますより大きな値を持つ理論それらの下位の理論の一貫性を証明し、そのようなすべての理論を可算無限スケール上に位置づける。[ 5 ]
ビジービーバー関数の成長特性は、物理的チャーチ＝チューリングのテーゼが正しいと仮定すると、物理システムの挙動に影響を与える。物理的チャーチ＝チューリングのテーゼが成り立ち、すべての物理的に計算可能な関数がチューリング計算可能であるならば、直接測定可能な物理量はビジービーバー関数よりも速く成長することはできず、チューリング計算可能な関数もビジービーバー関数よりも速く成長することはできない。[ 32 ]単純な関数また、成長率の下限だけでなく、収束率の上限と下限も課すことになるだろう。[ 33 ] [ 32 ]
1964年、ミルトン・グリーンは、1sカウント方式のビジービーバー関数の下限を開発し、1964年のIEEEスイッチング回路理論および論理設計シンポジウムの議事録に掲載した。ハイナー・マルクセンとユルゲン・ブントロックはこれを「非自明な（原始再帰的ではない）下限」と表現した。[ 34 ]この下限は計算可能だが、 nに関する単一の式で表すには複雑すぎる。[ 35 ]これは、それぞれが特定のnに対する下限を示すチューリングマシンのセットを用いて行われた。[ 35 ] n = 8の場合、この方法は次のようになる。
対照的に、現在の最良の下限値（2026年時点）はは、はクヌースの上向き矢印表記を表します。[ 36 ]これは. の価値おそらくそれよりもずっと大きいだろう。
グリーンの下限は、一連のチューリングマシンの再帰的構成によって示されました。各チューリングマシンは、入力テープに繰り返し適用される2つの追加状態を持つ、より小さなマシンで構成されていました。[ 35 ] の値を定義する -州の忙しいビーバーの競争相手がテープに収録されているなるべきもの（各機械の最終的な出力は、その価値である）（空白テープには 0 個の 1 があるため）再帰関係は次のようになります。[ 35 ] これにより、下限を計算するための2つの式が得られる。によって与えられた th マシン:
グリーンの下限はアッカーマン関数とも関連付けられる。特に、 すべての正の 整数に対して . [ 37 ]
自明なことに、S ( n ) ≥ Σ( n )である。なぜなら、 Σ( n )個の 1 を書き込む機械は、少なくともΣ( n )ステップを要しなければならないからである。[ 37 ] 1 の数 Σ ( n )を用いて、時間S ( n )の上限をいくつか与えることができる。
n状態チューリングマシンが任意の位置ではなく連続して出力できる1 の最大数(出力できる最大の単項数) としてnum( n )を定義することにより、 [ 37 ] [ 10 ]が示される。
Ben-AmramとPetersen（2002）は、 S（n）の漸近的に改善された境界も与えている。すべてのn ≥ 2に対して、定数cが存在する。 [ 37 ]
以下の表は、S ( n )、Σ( n )、およびその他のいくつかのビジービーバー関数の正確な値と既知の下限値を示しています。この表では、2シンボルチューリングマシンを使用しています。「?」と表示されているエントリは、左側の他のエントリ以上の大きさであり（すべてのn状態マシンは(n+1)状態マシンでもあるため）、その上のエントリより大きくはありません（S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)であるため）。したがって、space(6)は2より大きいことがわかっています。5、space(n) ≥ Σ(n) および Σ(6) > 25.47 176 870は space(5) の上限です。なぜなら S(5) =47 176 870 ( [ 3 ] ) および S(n) ≥ space(n)。4098 は num(5) の上限です。なぜなら Σ(5) = 4098 であり、Σ(n) ≥ num(n) だからです。最後に「?」と表示されているエントリは num(6) です。なぜなら Σ(6) > 2 だからです。5 ですが、Σ(n) ≥ num(n) であり、num(7) も同様です。
5 状態のビジービーバーは 1989 年に Heiner Marxen と Jürgen Buntrock によって発見されましたが、2024 年にオンラインのアマチュア数学者集団によってRocqで形式化された証明を使用して、5 番目のビジービーバーとして優勝したことが証明されました。[ 39 ] [ 40 ]
これらは、Σ(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しか生成しません。[ 15 ] )
結果: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107ステップ、合計13個の「1」)
結果： 47,176,870ステップ中に4098個の「1」と8191個の「0」が散在。
右側の画像を見ると、この解がいくつかのセルオートマトンにおける進化と質的に類似していることがわかります。
結果: 2↑↑↑5 ステップ以上で 2↑↑↑5 を超える "1" があり、2↑↑↑5 = 2↑↑2↑↑2↑↑2↑↑2 であり、↑↑ はテトラレーションを表します。
次の表では、各ビジービーバー（Σを最大化する）のルールが視覚的に表現されています。オレンジ色の四角はテープ上の「1」に対応し、白色は「0」に対応します。頭の位置は黒い楕円で示され、頭の向きが状態を表します。個々のテープは水平に配置され、時間は上から下へと進みます。停止状態は、1つの状態をそれ自身にマッピングするルール（頭が動かない）で表されます。
