S (5) = 47, 176, 870

5番目のビジービーバー

The fifth Busy Beaver value

1989年の週末に見つかった機械が、35年後に最長と決まった。

5つの状態のチューリング機械が、止まるまでに動ける最長の歩数。計算できない関数S(n)の5番目の値で、2024年にbbchallengeが確定させた。

年代: 1962〜2024年
習う: 大3以上・情報科学・計算可能性
レベル: 大学(例題 5 問)
人物: ティボール・ラドー、アラン・チューリング、シェン・リン、アレン・ブレイディ、ハイナー・マルクセン、ユルゲン・ブントロック、ゲオルギ・ゲオルギエフ、スコット・アーロンソン、トリスタン・ステラン、mxdys

数学情報科学哲学

逸話

6歩で止まる2行の表

状態が2つ、規則が4つだけの機械は、止まるまでに最長で何歩動けるか。2状態なら6歩で、紙と鉛筆でもたどれる。状態を5つに増やすと、最長は47,176,870歩になる。この値が確定したのは2024年で、確定させたのは、ネットに集まった数百人の共同研究bbchallengeだった。参加者の多くは、大学や研究所に属していない。

規則は表に書ける。行が状態、列が頭の下のマスの記号で、「1RB」は「1を書き、右へ1マス動き、状態Bになる」と読み、Zは止まることを表す。2状態の機械は、Aで0なら1RB、Aで1なら1LB、Bで0なら1LA、Bで1なら1RZである。すべてのマスが0のテープで状態Aから始めると、6歩目にBで1を読んで止まり、1が4個残る。

止まる機械は、動かせば止まったと分かる。厄介なのは止まらない機械のほうだ。100万歩動いても止まらない機械が、1億歩目に止まるかもしれない。いつまでも止まらないと言い切るには、1台ずつ理由が要る。

1983年1月、西ドイツのドルトムント大学で理論計算機科学の学会が開かれ、合わせて催された競技会に、5状態の機械が133台寄せられた。優勝したウーヴェ・シュルトの機械は、1を501個残して134,467歩で止まった。シュルトはパソコンに差し込む回路の板でチューリング機械を組み、1秒に約450万歩で候補を動かしていた。

1980年代はじめの机の上で、ふたを開けたパソコンに、ICが並ぶ手作りの回路の板を差し込む手元(画像生成 AI で描いたイメージ) — 1982年、シュルトはパソコンに差し込む回路の板でチューリング機械を組んだ（競技会の報告書による）画像生成AIで描いたイメージ

記録を大きく塗り替えたのは、ベルリンの大学院生のころから余暇に機械を探していたハイナー・マルクセンとユルゲン・ブントロックである。科学誌Quantaの取材によると、1989年、プログラマーとして働いていたマルクセンは、勤め先が入れた新しい計算機で、探索のプログラムを週末のあいだ動かした。見つかったのは、47,176,870歩で止まる機械だった。マルクセンはQuantaへのメールで、「何時間かバグを探したあと、探すのをやめて、不思議な気持ちになり始めた」と振り返っている。

週末の夕方、人のいない会社の計算機室で、男性が光る画面の前に立つ後ろ姿(画像生成 AI で描いたイメージ) — 1989年、マルクセンは勤め先の新しい計算機で、探索のプログラムを週末のあいだ動かした（Quantaによる）画像生成AIで描いたイメージ

それより長く動いて止まる機械が無いことは、誰も示せなかった。4状態の値を決めたアレン・ブレイディは、1990年の文章に「 $Σ (5) = 4, 098$ と $S (5) = 47, 176, 870$ が証明されることは決してない」という予言を書いている。予言は34年後に外れた。

起源

ビーバー狩りの60年

問いを立てたのは、ハンガリー生まれの数学者ティボール・ラドーである。MacTutorの伝記によると、ラドーは第一次世界大戦でロシア軍の捕虜となり、シベリアの収容所で、同じ捕虜だった数学者エドゥアルト・ヘリーに数学を学んだ。1930年からオハイオ州立大学で教え、石けん膜の形を問うプラトー問題を解いたことで知られる。

ティボール・ラドーの肖像(画像生成 AI で描いたイメージ) — ティボール・ラドー1895–1965計算できない関数の簡単な例として、ビジービーバーのゲームを考えた画像生成AIで描いたイメージ

晩年のラドーは、計算の理論に関心を移した。計算できない問題があることは、1936年のアラン・チューリングの論文から分かっていた。チューリングは、紙と鉛筆で計算する人の手順を、テープと頭と有限個の状態だけの機械に置き換えた。その議論から、どの機械についても止まるかどうかを判定する一般の手順は無いことが導かれる。いまは停止問題と呼ばれる結果である。

アラン・チューリングの肖像(Alan Turing (1951) (crop)) — アラン・チューリング1912–1954計算とは何かを定式化し、生き物の模様の数理にも挑んだ出典: Wikimedia Commons・Elliott & Fry・Public domain

1962年5月、ラドーは『Bell System Technical Journal』に、論文「計算できない関数について」を載せた。機械を状態の数で分けると、 $n$ 状態の機械は有限個しかない。0だけのテープから動かして止まる機械のうち、歩数の最大を $S (n)$ 、残る1の個数の最大を $Σ (n)$ とする。ラドーは、この最大を競う遊びを「ビジービーバー（忙しいビーバー）のゲーム」と名づけ、計算できない関数のごく簡単な例として示した。 $S (2) = 6$ も、この論文で示されている。

3状態では、ラドーの大学院生シェン・リンが1963年の博士論文で $S (3) = 21$ を示し、1965年に2人の共著で発表した。4状態について、ラドーは1963年に「いまのところ全く望みがないように見える」と書いた。

オレゴン州立大学の大学院生だったアレン・ブレイディは、途中まで同じ動きをする機械をひとまとめにし、動きが分かれるところでだけ枝分かれさせて数える方法を考えた。Quantaによると、1964年には、プログラムを動かす計算機を借りるため、約145 km離れたビーバートンの霊長類の研究所まで車で通った。

1960年代の研究所の計算機室で、大きな筐体と紙テープの読み取り機の前に立つ若い男性の後ろ姿(画像生成 AI で描いたイメージ) — 1964年、ブレイディは計算機を借りるため、約145 km先のビーバートンの研究所まで車で通った（Quantaによる）画像生成AIで描いたイメージ

ブレイディは1966年に107歩で止まる4状態の機械を見つけ、1974年に、それより長く動いて止まる機械が無いことを示した。学術誌『Mathematics of Computation』に載ったのは1983年である。ただ、最後まで残った機械については、長い記録を印刷して調べ、「どれも止まらないと筆者は納得した」と書いている。

5状態では、2003年にブルガリアのゲオルギ・ゲオルギエフが判定のプログラムを公開し、決められない機械は43台だと主張した。しかし、プログラムは説明の無いPascalで約6,000行あり、ほかの人が検証するのは難しかった。2020年、スコット・アーロンソンは、30年間記録が破られていないことから、 $S (5) = 47, 176, 870$ を予想として掲げた。

2022年3月、アイルランドの大学院でDNA計算を研究していたトリスタン・ステランが、共同研究のサイトbbchallenge.orgを開いた。参加者はチャットのDiscordで議論し、止まらない機械を見分けるプログラムを持ち寄った。どのプログラムも、別の参加者が独立に作り直して同じ結果を出すまで採用しなかった。

2024年5月10日、mxdysという名だけで知られる参加者が、「BB(5)のCoqの証明が終わった」と書き込んだ。Coq（いまの名はRocq Prover）は、証明の正しさを計算機に検査させる証明支援系である。その書き込みの19日前に、ブレイディは90歳で亡くなっていた。bbchallengeは7月2日に結果を発表し、2025年9月15日には、証明を人が読める形にした48ページの論文をarXivに公開した。

証明

計算できない数を、5まで決める

前半で $S (n)$ が計算できないことを、後半で $S (5)$ の決め方を示す。機械の状態・頭の位置・テープの中身の組を様相と呼び、機械 $M$ が0だけのテープから止まるまでの歩数を $s (M)$ と書く。止まる最後の1歩も数える。

表の1マスには、書く記号2通り、向き2通り、次の状態 $n$ 通りの組か、「止まる」が入る。マスは $2 n$ 個なので機械は有限個で、止まるものの歩数には最大がある。
$# {n 状態の機械} = (4 n + 1)^{2 n}, S (n) = M は止まる max s (M)$
1歩で書き換わるマスは1つなので、1の個数は1歩に1個までしか増えない。
$Σ (n) \leq S (n)$
$n$ 状態の機械は、使わない状態を1つ足せば $n + 1$ 状態の機械とみなせる。
$S (n) \leq S (n + 1), Σ (n) \leq Σ (n + 1)$
チューリングの議論で、停止問題が解けないことを示す。機械を $M_{1}, M_{2}, \dots$ と並べ、どの $M_{i}$ と入力 $j$ についても止まるかを答える手順 $H$ があったとする。 $H$ を使い、入力 $i$ を受けると、 $M_{i} (i)$ が止まるなら無限に回り、止まらないなら止まる機械 $D$ を作る。 $D$ も並びのどこかに $M_{k}$ として現れるので、 $i = k$ とおくと矛盾する。
$D (i) が止まる ⟺ M_{i} (i) が止まらない$

機械を行、入力を列に並べた表。対角線の答えを逆にした機械Dは、どの行とも対角線のマスで食い違う。

入力 $w$ を書き込む状態を前に付けた機械 $M_{w}$ を作れば、入力つきの問いは、0だけのテープの問いに置き換わる。0だけのテープから止まるかどうかも、判定できない。
$M (w) が止まる ⟺ M_{w} (空白) が止まる$
$S$ を計算する手順があれば、 $n$ 状態の機械を $S (n)$ 歩だけ動かし、止まっていなければ止まらないと答えられる。手順5と矛盾するので、 $S$ は計算できない。
$M が止まる ⟺ M は S (n) 歩以内に止まる$
$S$ は、計算できるどんな関数 $f$ よりも、いずれ大きくなる。1を $x$ 個書く $x$ 個の状態の後ろに、1の個数 $x$ を読んで $f (2 x)$ 個の1を書く $c$ 状態の機械をつなぐ。 $x \geq c$ なら手順2と3から次が成り立ち、奇数でも同じである。
$S (2 x) \geq Σ (2 x) \geq Σ (x + c) \geq f (2 x)$
ここから後半に移る。下から押さえるには、止まる機械を1台見せればよい。マルクセンとブントロックの機械を動かすと、47,176,870歩目に止まり、1が4,098個残る。
$S (5) \geq 47, 176, 870, Σ (5) \geq 4, 098$
上から押さえるには、数え上げた181,385,789台の集まり $T_{5}$ （途中の計算の章）のすべてについて、止まるかどうかを決める。止まる48,379,894台は、どれも47,176,870歩以内に止まることを動かして確認する。
$S (5) = max {s (M) : M \in T_{5}, M は止まる}$
止まらない証拠のいちばん簡単なものは、くり返しである。同じ様相に2度来たら、その間の動きを永久にくり返す。一方へ進みながら同じ形に戻る機械も、行く先のマスはいつも0なので、同じ動きを続ける。後者はリンが1963年の博士論文で扱った型で、この2種類で126,994,099台が止まらないと決まった。
$c_{i} = c_{j} (i < j) ⟹ c_{i + t} = c_{j + t} (t \geq 0)$

くり返さない機械には、閉じた集合を使う。様相の集合 $C$ が最初の様相 $c_{0}$ を含み、1歩進めても $C$ から出ず、止まる様相を含まなければ、機械は止まらない。 $C$ を有限オートマトンで表し、計算機に探させる方法で6,011,742台、重みつきの版で17台が決まった。
$c_{0} \in C, c \in C, c \to c^{'} ⟹ c^{'} \in C, C \cap Halt = \emptyset$
どの方法でも決まらなかった13台は、1台ずつ証明した。スケレット1号と呼ばれる機械は、 $5.41 \times 1 0^{51}$ 歩を超える不規則な動きのあとで、ようやくくり返しに入る。最初に0を書く24台は、最初に1を書く機械に置き換えて、同じ証明を使った。こうして、止まらない133,005,895台がすべて片づく。
$S (5) \leq 47, 176, 870$
手順8と12を合わせる。数え上げも判定もCoqの中で実行し、Coqが証明を検査した。使う公理は、関数の外延性だけである。
$S (5) = 47, 176, 870$

途中の計算

16.7兆台を1.8億台に減らす

5状態の機械を数え、bbchallengeが調べた台数まで減らす。

1マスに入る遷移を数える
$2 \times 2 \times 5 + 1 = 21$
表の10マスぶん掛ける
$2 1^{10} = 16, 679, 880, 978, 201$
BからEの名前の付け替えで割る
$\frac{2 1 ^{10}}{4 !} \approx 6.9 \times 1 0^{11}$
最初の一手を右へ動くものに限る
$\frac{6.9 \times 1 0 ^{11}}{2} \approx 3.5 \times 1 0^{11}$
動いて使った遷移だけを順に決めて数える
$181, 385, 789$
減った割合を求める
$\frac{16 , 679 , 880 , 978 , 201}{181 , 385 , 789} \approx 91, 958$

最初の遷移を決めると4通りに分かれる。0RAと1RAは右へ進み続けて止まらず、0RBと1RBは次に使う遷移を12通りに決めて枝を伸ばす。

手順4までで減るのは48分の1にすぎない。大きいのは手順5で、ブレイディが考えた木の形の数え方（木正規形、Tree Normal Form）による。たとえば最初の手を「0を書いて右へ、Aのまま」と決めた機械は、0を読み続けて右へ進むだけなので、残り9マスの中身にかかわらず止まらない。 $2 1^{9}$ 台、約7,900億台が1台にまとまる。

応用

4,718万歩を41秒で動かす

止まる機械の確認は、思ったより軽い。テープを辞書に書き込むだけの素朴なシミュレーターをPython 3.14で書き、編集部のサーバーでマルクセンとブントロックの機械を動かすと、約41秒で47,176,870歩目に止まった。1は4,098個、使ったマスは12,289個で、論文の値と一致する。

重いのは、止まらない側の証明だ。Coq-BB5はCoqで27,274行、補題は638個ある。普通のノートパソコンで約13時間かかったが、木を12本の枝に分けて並列にし、速い計算エンジンに切り替えると、13コアで約45分になった。結果を信じるために人が読むのは、定理の主張と定義を書いた121行のファイルだけで、Coqの知識は要らないと論文は書いている。

閉じた集合 $C$ は、プログラムの検証で使うループ不変条件と同じ形をしている。最初に成り立ち、1回まわしても崩れず、終了の条件と両立しない性質を1つ見つければ、そのループは終わらないと言える。bbchallengeの判定器は、この性質を機械ごとに自動で探した。

例題と解説

小さな機械を手で動かす

停止問題と対角線論法は、大学の計算理論の講義で学ぶ。名古屋大学情報学部の3年の講義「計算理論」は、チューリング機械から始まり、対角線論法による判定不能性の証明、還元による証明法へと進む。

例題 1基本もう1台の6歩の機械

2状態の機械で、Aで0なら1RB、Aで1なら止まる（1RZ）、Bで0なら1LB、Bで1なら1LAとする。0だけのテープで状態Aから動かし、止まるまでの歩数と、残る1の個数を求めよ。

解説を見る

頭の位置を0から数え、1歩ずつ追う。

Aで0を読む。1を書いて右へ動き、Bになる。頭は1。
Bで0を読む。1を書いて左へ動き、Bのまま。頭は0。
Bで1を読む。1のまま左へ動き、Aになる。頭は−1。
Aで0を読む。1を書いて右へ動き、Bになる。頭は0。
Bで1を読む。左へ動き、Aになる。頭は−1。
Aで1を読み、止まる。
$s (M) = 6, 1 の個数 = 3$

歩数は $S (2) = 6$ に届くが、1は3個で、本文の機械の4個より少ない。3状態でも、最長の21歩の機械は1を5個しか残さず、 $Σ (3) = 6$ は11〜14歩で止まる別の5台が出す。

例題 2基本3状態の機械の数

（1）3状態・2記号の機械は何台あるか。「止まる」も1マスの選び方に数える。

（2）bbchallengeと同じ数え方では、3状態の機械は5,417台にまとまる。何分の1になったか、小数第1位を四捨五入して答えよ。

解説を見る

（1）1マスの選び方は $2 \times 2 \times 3 + 1 = 13$ 通りで、マスは6個ある。

1 3^{6} = 4, 826, 809

（2）割り算をする。

\frac{4 , 826 , 809}{5 , 417} = 891.04 \dots

約891分の1である。5状態では約91,958分の1になる。

例題 3入試矢印で書く大きな数

$a ↑ b = a^{b}$ とし、 $a ↑↑ b$ は $a$ を $b$ 個重ねたべき乗の塔、 $a ↑↑↑ b$ は $b$ 個の $a$ を $↑↑$ でつないだものとする。どれも右から計算する。

（1） $2 ↑↑ 3$ と $2 ↑↑ 4$ を求めよ。

（2） $2 ↑↑↑ 3$ を求めよ。

（3） $2 ↑↑ 5$ は10進法で何桁か。 $lo g_{10} 2 = 0.30103$ とする。

解説を見る

（1）塔を上から計算する。

2 ↑↑ 3 = 2^{2^{2}} = 16, 2 ↑↑ 4 = 2^{16} = 65, 536

（2）右から計算する。

2 ↑↑↑ 3 = 2 ↑↑ (2 ↑↑ 2) = 2 ↑↑ 4 = 65, 536

（3） $2 ↑↑ 5 = 2^{65, 536}$ である。

65, 536 \times 0.30103 = 19, 728.3 \dots

19,729桁になる。 $2 ↑↑↑ 4 = 2 ↑↑ 65, 536$ は2を65,536個重ねた塔で、6状態の下限 $2 ↑↑↑ 5$ は、さらにその先にある。

例題 4難関狭い範囲を動く機械

$n$ 状態の機械が、0だけのテープから動き、頭はずっと連続する $k$ マスの中にとどまるとする。

（1）現れうる様相は何通りか。

（2） $nk 2^{k}$ 歩動いても止まらなければ、永久に止まらないことを示せ。

（3） $n = 5$ 、 $k = 10$ のとき、何歩まで見ればよいか。

解説を見る

（1）状態が $n$ 通り、頭の位置が $k$ 通り、 $k$ マスの中身が $2^{k}$ 通りある。外のマスは0のままなので、様相は $nk 2^{k}$ 通りである。

（2）止まらずに $nk 2^{k}$ 歩動くと、最初を含めて $nk 2^{k} + 1$ 個の様相が現れる。（1）より、鳩の巣原理で同じ様相が2度現れ、証明の手順10により、その間の動きを永久にくり返す。

（3）掛け算をする。

5 \times 10 \times 2^{10} = 51, 200

51,200歩動いて止まらなければ、止まらない。範囲の外へ出ていく機械には、この議論は使えない。

例題 5大学アンチハイドラの数列

$H (x) = ⌊ 3 x /2 ⌋$ とし、 $x_{0} = 8$ 、 $x_{t + 1} = H (x_{t})$ とする。6状態の機械アンチハイドラは、 $x_{0}$ から順に見て、奇数の個数が偶数の個数の2倍を超えたときにだけ止まる。

（1） $x_{0}$ から $x_{11}$ までを求めよ。

（2）（1）の12項で、奇数と偶数はそれぞれ何個か。この範囲で機械が止まらないことを確かめよ。

解説を見る

（1）偶数なら $3 x /2$ 、奇数なら $(3 x - 1) /2$ を計算する。

8, 12, 18, 27, 40, 60, 90, 135, 202, 303, 454, 681

（2）奇数は27、135、303、681の4個、偶数は8個である。最初の3項はどれも偶数で、そのあとのどの時点でも、奇数の個数は偶数の個数の2倍を超えない。

4 \leq 2 \times 8

図示

6、21、107、47,176,870

状態の数と、止まる機械の最長の歩数。縦軸は対数の目盛りで、値が論文や発表で示された年を添えた。6状態は2↑↑↑5より大きいことしか分かっていない。

4状態から5状態に移ると、最長の歩数は約44万倍になる。6状態の下限 $2 ↑↑↑ 5$ は、この縦軸のどこにも描けない。

181,385,789台が、どの方法で止まる・止まらないと決まったか。棒の長さは台数の対数で表した。

くり返しを調べる段階で、止まる機械も含めて96.7%が片づく。1台ずつ証明した13台のうち、スケレット17号のCoqの証明は、それだけで7,000行近い。

シミュレーション

テープを1歩ずつ書き換える

「機械」で、2状態から5状態までの最長の機械を選ぶ。表で塗られたマスが次に使う規則で、下の図は1行が1歩、塗ったマスが1、点が頭の位置を表す。5状態では1行に約11.8万歩をまとめ、1の多さを網点の濃さで描く。「速さ」を30にすると、47,176,870歩で止まるまでを約7秒で早送りする。

広がる学問

予想を機械に置き換える

数学「すべての $x$ について、計算機で確認できる性質が成り立つ」という形の予想は、反例を探して見つかれば止まる機械に書き換えられる。ゴールドバッハ予想は25状態、リーマン予想は744状態の機械になり、エルデシュが立てた数論の予想には15状態で足りる。 $S (25)$ が分かれば、ゴールドバッハ予想の機械を $S (25)$ 歩動かすだけで決着がつく。
情報科学 プログラムが止まるかを調べる解析では、どんなプログラムにも正しく答えて必ず止まる手順は作れない。bbchallengeの判定器は「止まる・止まらない・分からない」の3つを返すことで、この壁をかわした。Coq-BB5は、証明支援系の中でアルゴリズムを動かし、その出力を証明に使う「リフレクションによる証明」で、四色定理のCoqの証明と同じ種類にあたる。計算にかかる手間を測る計算量の理論も同じ模型から始まり、ショアのアルゴリズムの論文は、チューリング機械でどれだけ速く計算できるかという問いから話を起こしている。
哲学集合論の公理系ZFに矛盾が無いことも、ZFの証明を順に並べて矛盾を探す機械に置き換えられ、その機械は748状態で作られている。ゲーデルの第2不完全性定理から、ZFに矛盾が無いかぎり、ZFの中では $S (748)$ の値を証明できない。アーロンソンは、 $S (20)$ でもZFでは証明できないと予想している。知りうることの境目が、状態の数で語られるようになった。

いまの研究と事業

6状態のビーバーを追う

2025年mxdys（bbchallenge）6状態で、 $2 ↑↑↑ 5$ 歩より長く動いて止まる機械を見つけた。この機械が止まることは、Coqで証明されている。 $S (6)$ の下からの評価は、証明の手順8と同じく1台示せば上がる。上から決めるには約330億台を数え上げて判定する必要があり、2026年3月の論文の改訂の時点で、約1,214台が残っている。出典はarXiv:2509.12337とBusyBeaverWikiの「BB(6)」。
2024年mxdys、Racheline（bbchallenge）6状態の残りの中から、止まるかどうかが、 $H (x) = ⌊ 3 x /2 ⌋$ をくり返すコラッツ予想に似た問い（例題5）と同じになる機械アンチハイドラを見つけた。確率の見積もりでは止まる見込みは $1 0^{- 200, 000, 000}$ を下回るが、証明は無く、 $S (6)$ を決めるにはこの問いを解く必要がある。出典は上の論文の付録Cと、科学誌Quantaの2024年7月2日の記事。
2024年bbchallenge（記号を増やした機械）2状態・4記号の値 $S (2, 4) = 3, 932, 964$ を、Coq-BB5の中で証明した。3状態・3記号と2状態・5記号の残りにも、コラッツ型の機械（ビッグフット、ハイドラ）が見つかっている。出典は上の論文の表1と付録C。
2024〜2025年テレンス・タオら（Equational Theories Project） マグマと呼ばれる、2項演算を1つ持つ集合の等式の法則を調べた。最も単純な4,694個の法則の間にある含意22,028,942個をすべて決め、人の証明と自動の証明を組み合わせた全体を、証明支援系Leanで検証した。問いを1つずつ判定し、全体を機械に検査させる点で、 $T_{5}$ を調べたbbchallengeと同じ形である。出典はarXiv:2512.07087。
2024年Amazon Web Services（Cedar） 認可の規則を書く言語Cedarを、一般のループを持たない形に設計し、評価が必ず止まるようにした。規則をSMTの論理式に直す変換は決定可能で、健全かつ完全であることをLeanで証明し、AWSの製品で使っている。手順6のとおり一般のプログラムの停止は判定できないので、言語の側を狭めて、問いが必ず決着するようにした例である。出典はarXiv:2403.04651。

参考文献

T. Radó, "On Non-Computable Functions", Bell System Technical Journal 41 (1962), 877-884; A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proc. London Math. Soc. (2) 42 (1937), 230-265.
S. Lin, T. Radó, "Computer Studies of Turing Machine Problems", J. ACM 12 (1965), 196-212; A. H. Brady, "The determination of the value of Rado's noncomputable function Σ(k) for four-state Turing machines", Math. Comp. 40 (1983), 647-665.
J. Ludewig, U. Schult, F. Wankmüller, "Chasing the Busy-Beaver: Notes and Observations on a Competition to Find the 5-state Busy Beaver", Bericht Nr. 159, Universität Dortmund (1983); H. Marxen, J. Buntrock, "Attacking the Busy Beaver 5", Bull. EATCS 40 (1990), 247-251; S. Aaronson, "The Busy Beaver Frontier", ACM SIGACT News 51(3) (2020), 32-54.
The bbchallenge Collaborationほか, "Determination of the fifth Busy Beaver value", arXiv:2509.12337（2025年9月15日、第2版は2026年3月23日）; mxdys, Coq-BB5（https://github.com/ccz181078/Coq-BB5）.
The bbchallenge Collaboration, "[July 2nd 2024] We have proved BB(5) = 47,176,870"（discuss.bbchallenge.org、2024年7月2日）; The bbchallenge Collaborationほか, "Turing machines deciders, part I", arXiv:2504.20563; BusyBeaverWiki, "BB(6)".
B. Brubaker, "With Fifth Busy Beaver, Researchers Approach Computation's Limits", Quanta Magazine（2024年7月2日）; MacTutor History of Mathematics, "Tibor Radó".
M. Bolanほか, "The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale", arXiv:2512.07087; J. W. Cutlerほか, "Cedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization", arXiv:2403.04651; 名古屋大学情報学部「計算理論」シラバス（時間割コード1001329）.

5番目のビジービーバー

6歩で止まる2行の表

ビーバー狩りの60年

計算できない数を、5まで決める

16.7兆台を1.8億台に減らす

4,718万歩を41秒で動かす

小さな機械を手で動かす

例題 1基本もう1台の6歩の機械

例題 2基本3状態の機械の数

例題 3入試矢印で書く大きな数

例題 4難関狭い範囲を動く機械

例題 5大学アンチハイドラの数列

6、21、107、47,176,870

テープを1歩ずつ書き換える

予想を機械に置き換える

6状態のビーバーを追う

参考文献

タグ

同じタグを持つ公式

姉妹サイト