ビジービーバー(busy beaver)とは、状態が $n$ 個の 2 記号の Turing 機械のうち空白のテープから停止するものについて、停止したときテープに残る $1$ の個数の最大値 $\Sigma(n)$ と停止までのステップ数の最大値 $S(n)$ を考える問題で、Radó が 1962 年に導入した。$n$ 状態の機械は有限個なので値は定まるが、$\Sigma$ と $S$ はどの計算可能関数よりも最終的に大きく、計算できない。$S$ の上界が計算できれば停止問題が解け、計算可能で健全な理論は無限個の $n$ で値を決められない。$S(5)=47{,}176{,}870$ が証明支援系で検証されている。
ビジービーバー(busy beaver)は、状態の数を $n$ に固定した 2 記号の Turing 機械のうち、空白のテープから出発して停止するものの中で、停止したときテープに残る $1$ の個数の最大値 $\Sigma(n)$ と、停止までのステップ数の最大値 $S(n)$ を考える問題である。T. Radó が 1962 年に「計算できない関数のごく簡単な例」として導入した(Rad62 pp. 877–880)。$n$ 状態の機械は有限個しかないので $\Sigma(n)$ と $S(n)$ はきちんと定まった自然数だが、関数 $n\mapsto\Sigma(n)$ はどの 計算可能関数 よりも速く増え、したがって計算できない(Rad62 p. 881)。
計算できない関数の存在だけなら、機械の個数を数える 対角線論法 で分かる(Turing機械 の定理「Turing 計算可能でない関数の存在」)。ビジービーバーは、具体的に定義された 1 つの関数が計算できないことを、「有限集合には最大元がある」という原理と機械の合成だけで示す例である(Rad62 p. 877 の序文)。
この記事では、Radó の流儀で機械と $\Sigma(n)$・$S(n)$ を定義し、次を証明する。$S(n)\ge\Sigma(n)$ と $\Sigma(n+1)>\Sigma(n)$(prop-bb-basic)、$\Sigma(1)=S(1)=1$(prop-bb-one)、$\Sigma$ がどの計算可能関数よりも最終的に大きいこと(thm-bb-dominates)、$S$ の上界が計算できれば停止問題が解けること(prop-bb-halting)、計算可能な理論は $\Sigma(n)$ の値を有限個を除いて決められないこと(thm-bb-unprovable)。小さい $n$ での値は表にまとめる。
$\mathbb{Z}$ で添字づけたテープの各マスに $0$ か $1$ が書かれ、有限個のマスを除いて $0$ であるとする。$0$ を空白とみなす。
$n\ge1$ とする。$n$ 状態の機械 とは、状態の集合 $\{1,\dots,n\}$($1$ が初期状態)と、各組 $(q,a)\in\{1,\dots,n\}\times\{0,1\}$ に対する 指示 $\delta(q,a)=(b,D,q')$($b\in\{0,1\}$、$D\in\{\mathrm{L},\mathrm{R}\}$、$q'\in\{0,1,\dots,n\}$)の組である。状態 $q$ でヘッドが記号 $a$ を読むとき、機械はそのマスに $b$ を書き、ヘッドを $D$ の向きに 1 マス動かし、状態 $q'$ に移る。これを 1 ステップ と数える。$q'=0$ のときは、書いて動いたあとで 停止 する(Rad62 pp. 877–878)。
どの指示も必ず書いて動く。停止する指示も 1 ステップと数え、その指示も記号を書く。これが Radó の流儀である(Rad62 p. 878)。指示の選び方は 1 組あたり $2\cdot2\cdot(n+1)$ 通りで組は $2n$ 個なので、$n$ 状態の機械はちょうど $(4(n+1))^{2n}$ 個ある(Rad62 p. 880 の式 (1))。
Turing機械 の記事の定義との違いは 3 つある。テープ記号は $0,1$ だけで、ヘッドは必ず動き、停止は「指示が定義されていない」ことではなく停止の指示で表す。停止の指示を「読んだ記号を書き戻して動く」ものに置き換えれば、指示が定義されていない組で止まる機械も同じ $1$ の個数で表せる。
$n$ 状態の機械 $M$ を、すべてのマスが $0$ のテープの上で、状態 $1$ から出発させる。停止するとき、停止までのステップ数を $s(M)$、停止したときテープにある $1$ の個数を $\sigma(M)$ とする。
$$
\Sigma(n)=\max\{\sigma(M)\},\qquad S(n)=\max\{s(M)\}
$$
と定める。最大は、空白のテープから停止する $n$ 状態の機械 $M$ 全体にわたってとる。$\Sigma$ を ビジービーバー関数(Radó の $\Sigma$ 関数)、$S$ を 最大シフト関数 という($\Sigma$ は Rad62 p. 880 の式 (3)、$S$ は同 §VI、pp. 882–883。Aar20 p. 2)。
停止する機械は少なくとも 1 つある(状態 $1$ で $0$ を読んだら停止する機械)。機械は有限個なので、最大は存在する。ただし、どの機械が停止するかを有限の手順で判定できるとは限らないので、最大が存在することと、最大を求める手順があることは別である。
文献によって流儀が違う。Aar20 は $S(n)$ を $\mathrm{BB}(n)$ と書き、停止の指示は書かず動かないとする(p. 1 の脚注 3)。bbc25 は指示が定義されていない組で止まるとし、停止のステップを数に含める(p. 9)。$S$ の値はどの流儀でも同じだが、$\Sigma$ は停止の指示が $1$ を書けるかで $1$ だけ違いうる(ex-bb-five)。この記事の値はすべて Radó の流儀による。
状態を $\mathrm{A}=1$、$\mathrm{B}=2$ と書き、停止を $\mathrm{H}$ と書く。
$$
\delta(\mathrm{A},0)=(1,\mathrm{R},\mathrm{B}),\quad\delta(\mathrm{A},1)=(1,\mathrm{L},\mathrm{B}),\quad\delta(\mathrm{B},0)=(1,\mathrm{L},\mathrm{A}),\quad\delta(\mathrm{B},1)=(1,\mathrm{R},\mathrm{H})
$$
とする。ヘッドの位置を $0$ から始めると、各ステップの後の(状態、ヘッドの位置、$1$ のあるマス)は
$$
(\mathrm{B},1,\{0\}),\ (\mathrm{A},0,\{0,1\}),\ (\mathrm{B},-1,\{0,1\}),\ (\mathrm{A},-2,\{-1,0,1\}),\ (\mathrm{B},-1,\{-2,-1,0,1\}),\ (\mathrm{H},0,\{-2,-1,0,1\})
$$
と進み、6 ステップで停止して $1$ が 4 個残る。よって $\Sigma(2)\ge4$、$S(2)\ge6$ である(Aar20 p. 2 の図 1、Bil03 Example 12.4、p. 84)。
$n\ge1$ について次が成り立つ。
1:停止する機械 $M$ では、各ステップでちょうど 1 つのマスに書くので、$1$ が書かれたことのあるマスは $s(M)$ 個以下である。最初のテープはすべて $0$ なので、停止したとき $1$ のあるマスは書かれたことのあるマスに限られ、$\sigma(M)\le s(M)\le S(n)$ である。$\sigma(M)=\Sigma(n)$ となる $M$ をとれば $\Sigma(n)\le S(n)$ を得る。次に、状態 $q< n$ で $0$ を読んだら $(1,\mathrm{R},q+1)$、状態 $n$ で $0$ を読んだら $(1,\mathrm{R},0)$ とする機械($1$ を読んだときの指示は何でもよい)は、右へ進みながら毎回新しい $0$ のマスを読み、$n$ ステップで $1$ を $n$ 個書いて停止する。よって $\Sigma(n)\ge n$。
2:$n$ 状態の機械 $M$ で $\sigma(M)=\Sigma(n)$ となるものをとる。$M$ の停止の指示 $(b,D,0)$ をすべて $(b,D,n+1)$ に替え、新しい状態 $n+1$ の指示を
$$
\delta(n+1,1)=(1,\mathrm{R},n+1),\qquad\delta(n+1,0)=(1,\mathrm{R},0)
$$
とする。この $(n+1)$ 状態の機械は、$M$ が停止する時点までは $M$ と同じに動き、そのあと状態 $n+1$ で $1$ の上を右へ進む。$1$ のマスは有限個なので、いつか $0$ を読み、そこに $1$ を書いて停止する。テープの $1$ は $M$ の停止時より 1 個多いので、$\Sigma(n+1)\ge\Sigma(n)+1$ である。$S$ については、$s(M)=S(n)$ となる $M$ の停止の指示を状態 $n+1$ への指示に替え、状態 $n+1$ の指示を 2 つとも停止の指示にすれば、ステップ数がちょうど 1 増える。$\square$
2 の証明は Bil03 Problem 12.3 (4)(p. 84)とその略解(p. 103)の方針に従った。
$\Sigma(1)=S(1)=1$ である。
1 状態の機械は、最初に状態 $1$ で $0$ を読む。$\delta(1,0)$ が停止の指示なら 1 ステップで停止し、$1$ は高々 1 個である。$\delta(1,0)=(b,D,1)$ なら、ヘッドは向き $D$ に動き続け、毎回まだ書いていない $0$ のマスを状態 $1$ で読むので、同じ指示が繰り返されて停止しない。よって停止する機械は 1 ステップで止まり、$S(1)\le1$、$\Sigma(1)\le1$ である。$\delta(1,0)=(1,\mathrm{R},0)$ の機械で等号が成り立つ。$\square$
これより大きい $n$ では、停止しない機械を 1 つずつ停止しないと証明する必要があり、手間が急に増える。知られている値は次のとおりである。
| $n$ | $S(n)$ | $\Sigma(n)$ | 出典 |
|---|---|---|---|
| 1 | 1 | 1 | prop-bb-one |
| 2 | 6 | 4 | Lin 1963(Aar20 p. 9 の表) |
| 3 | 21 | 6 | Lin 1963(同) |
| 4 | 107 | 13 | Brady 1983(同) |
| 5 | 47,176,870 | 4,098 | bbchallenge の共同研究(bbc25 Theorem 1.1、p. 2、Theorem 6.1、p. 37) |
$n=5$ の値の下界は Marxen と Buntrock が 1989 年に見つけた機械による(bbc25 p. 2。Aar20 p. 9 の表は 1990 年の論文を挙げる)。それが最大であることは、bbchallenge の共同研究が、調べる必要のある 5 状態の機械 181,385,789 個のそれぞれについて停止するかどうかを決め、証明支援系 Coq で検証して示した(bbc25 p. 1、p. 2。2025 年に公開されたプレプリント)。$\Sigma(5)=4{,}098$ は、Coq の証明から取り出した機械の一覧を使って計算された(同 Theorem 6.1 の証明、p. 37)。$n=6$ では、2020 年の時点で $S(6)>7.4\times10^{36534}$ という下界が知られていた(Aar20 p. 9 の表)。
状態を $\mathrm{A},\dots,\mathrm{E}$ とし、指示を「書く記号・向き・次の状態」の順に書く。
$$
\begin{array}{c|ccccc}
& \mathrm{A} & \mathrm{B} & \mathrm{C} & \mathrm{D} & \mathrm{E}\\\hline
0 & 1\mathrm{RB} & 1\mathrm{RC} & 1\mathrm{RD} & 1\mathrm{LA} & 1\mathrm{RH}\\
1 & 1\mathrm{LC} & 1\mathrm{RB} & 0\mathrm{LE} & 1\mathrm{LD} & 0\mathrm{LA}
\end{array}
$$
この機械は空白のテープから 47,176,870 ステップで停止する(bbc25 p. 9 の図 1、Aar20 p. 10 の表)。最後のステップは状態 $\mathrm{E}$ で $0$ を読む停止の指示で、停止の直前のテープには $1$ が 4,097 個ある。Radó の流儀では停止の指示が $1$ を書くので、停止したとき $1$ は 4,098 個になる。
関数 $f,g\colon\mathbb{N}\to\mathbb{N}$ について、ある $N$ があって $n\ge N$ なら $f(n)>g(n)$ となるとき、$f$ は $g$ より 最終的に大きい という(Rad62 pp. 880–881 の記号 $f(x)>-g(x)$)。
証明では、計算可能な関数をこの記事の流儀の機械で計算する。次の意味で使う。
$G\colon\mathbb{N}\to\mathbb{N}$ とし、$M$ をこの記事の流儀の機械とする。各 $x\in\mathbb{N}$ について、マス $1,\dots,x$ に $1$、ほかのマスに $0$ を書いたテープの上で、ヘッドをマス $0$ に置いて状態 $1$ から出発させると、$M$ が停止し、停止したときテープにある $1$ がちょうど $G(x)$ 個であるとき、$M$ は $G$ を 計算する という。
$G$ が 計算可能関数 なら、$G$ を計算するこの流儀の機械がある。これは Turing機械 の記事の定義で $G$ を計算する機械を、記号を $0,1$ に限り、停留をなくし、停止を停止の指示で表し、入力の位置を 1 マスずらした機械に作り替えられることによる。こうした流儀の違いが計算できる関数の全体を変えないことは Turing機械 の節「変種と頑健性」による(OLT26 §31.9、pp. 490–492。この記事では証明しない)。Rad62 p. 881 も同じ事実を Kleene の教科書に拠って使っている。
$f\colon\mathbb{N}\to\mathbb{N}$ を計算可能関数とする。ある $N$ があって、$n\ge N$ ならば $\Sigma(n)>f(n)$ である(Rad62 p. 881 の Theorem)。とくに $\Sigma$ は計算可能でない。$S\ge\Sigma$(prop-bb-basic)なので、$S$ も同じ性質をもち、計算可能でない。
単調な関数に取り替える。 $F(x)=\max\{f(0),\dots,f(x)\}$ とおく。$F$ は計算可能で、$F(x)\ge f(x)$、$F$ は単調非減少である。さらに $G(x)=F(2x)+1$ とおく。$G$ も計算可能なので、$G$ を計算する $c$ 状態の機械 $M_G$ がある(def-bb-computes)。$c$ は $f$ だけで決まり、$n$ によらない。
$n$ 個の 1 を書いてから $M_G$ を動かす。 $n\ge1$ とし、$n+c$ 状態の機械 $P_n$ を作る。状態 $1,\dots,n$ では、$0$ を読んだら
$$
\delta(q,0)=(1,\mathrm{L},q+1)\quad(1\le q\le n)
$$
とする($1$ を読んだときの指示は何でもよい)。状態 $n+1,\dots,n+c$ には $M_G$ の状態 $1,\dots,c$ を番号を $n$ ずらして置き、$M_G$ の指示の次の状態も $n$ ずらす(停止の指示はそのまま)。
空白のテープでヘッドの位置を $0$ から始めると、$P_n$ は状態 $q=1,\dots,n$ で毎回新しい $0$ のマスを読み、マス $0,-1,\dots,-(n-1)$ に $1$ を書いて、状態 $n+1$ でマス $-n$ にいる。テープの位置を $n$ だけ右にずらして見ると、これは $1$ がマス $1,\dots,n$ にあり、ヘッドがマス $0$ にある状態で $M_G$ を出発させた様子と同じである。機械の動きはテープの位置の平行移動で変わらないので、$P_n$ はそこから $M_G$ と同じに動いて停止し、テープには $1$ がちょうど $G(n)$ 個残る。よって
$$
\Sigma(n+c)\ \ge\ \sigma(P_n)=G(n)=F(2n)+1\qquad(n\ge1)
$$
である。
比べる。 $N=2c+1$ とし、$m\ge N$ をとる。$n=m-c$ とおくと $n\ge c+1\ge1$ で、$2n=m+(n-c)\ge m$ なので、$F$ の単調性から
$$
\Sigma(m)=\Sigma(n+c)\ \ge\ F(2n)+1\ >\ F(2n)\ \ge\ F(m)\ \ge\ f(m)
$$
である。
計算できないこと。 $\Sigma$ が計算可能なら、$f=\Sigma$ として、十分大きい $m$ で $\Sigma(m)>\Sigma(m)$ となって矛盾する。$S$ については、$m\ge N$ で $S(m)\ge\Sigma(m)>f(m)$ である。$\square$
証明の骨組みは Rad62 pp. 881–882 に従った。Radó は $F(x)=\sum_{i=0}^{x}(f(i)+i^2)$ をとり、$1$ を $x+1$ 個書く機械のあとに $F$ を計算する $C$ 状態の機械を 2 回つないで $\Sigma(1+x+2C)\ge3+x+F(x)+F(F(x))$(式 (8)、p. 882)を導く。ここでは $F(2x)+1$ を 1 回計算する形に書き換えた。どちらでも要点は、入力を書く部分の状態数が $n$ に比例して増えるのに対し、つなぐ機械の状態数 $c$ は一定で、出力は $n$ よりずっと速く増やせることである。
thm-bb-dominates から、$\Sigma(n)$ は Ackermann関数 $n\mapsto A(n,n)$ を含むどの計算可能関数よりも最終的に大きい。一方で、各 $n$ について $\Sigma(n)$ が 1 つの自然数として存在することは変わらない。計算できないのは、$n$ を受け取って $\Sigma(n)$ を出す 1 つの手順である。
$h\colon\mathbb{N}\to\mathbb{N}$ がすべての $n\ge1$ で $h(n)\ge S(n)$ を満たし、計算可能であるとする。すると、$n$ 状態の機械 $M$ を受け取って、$M$ が空白のテープから停止するかを判定する手順がある。そのような $h$ は存在しない(Aar20 Proposition 1、p. 4)。
$M$ を $h(n)$ ステップまで動かす。その間に停止すれば「停止する」と答える。停止しなければ、$M$ は停止しない。停止するなら $s(M)\le S(n)\le h(n)$ だからである。どちらも有限の手順である。後半:$h(n)\ge S(n)\ge\Sigma(n)$ なので、$h$ が計算可能なら thm-bb-dominates を $f=h$ に使って、十分大きい $m$ で $\Sigma(m)>h(m)\ge\Sigma(m)$ となり矛盾する。$\square$
逆に、空白のテープからの停止を判定する手順が使えれば、$n$ 状態の機械を全部並べ、停止するものだけを動かして $S(n)$ と $\Sigma(n)$ を計算できる(Aar20 p. 4)。したがって $S$ を計算することは、空白のテープからの 停止問題 を解くことと同じ難しさである。空白のテープからの停止の判定ができないことは、thm-bb-dominates とこの命題からも分かる。
計算できないことは、値を証明できないことにもつながる。$T$ を、公理の集合が計算可能な(定理を機械的に列挙できる)理論とする。Peano算術 や ZFC のように算術を表せる理論では、各 $n,k$ について「$\Sigma(n)=k$」を表す文が書ける。$T$ が この形の文について健全 であるとは、$T$ が証明する「$\Sigma(n)=k$」の形の文がすべて正しいことをいう。
$T$ を、公理の集合が計算可能で、「$\Sigma(n)=k$」の形の文について健全な理論とする。すると、どの $k$ についても $T$ が「$\Sigma(n)=k$」を証明しないような $n$ が無限個ある。
そのような $n$ が有限個しかないとする。すると $N_0\ge1$ があって、$n\ge N_0$ ならある $k$ について $T$ は「$\Sigma(n)=k$」を証明する。次の手順を考える。$n< N_0$ なら、有限個の値 $\Sigma(1),\dots,\Sigma(N_0-1)$ を表にしておいて答える。$n\ge N_0$ なら、$T$ の定理を順に列挙し、「$\Sigma(n)=k$」の形の定理が現れたらその $k$ を答える。仮定からこの探索は止まり、健全性から答えは $\Sigma(n)$ に等しい。これは $\Sigma$ を計算する手順なので、thm-bb-dominates に反する。$\square$
この証明は Aar20 p. 6 の「もう 1 つの証明」と同じ考え方である。Aar20 Proposition 3(p. 5)は $S$ について、算術の文について健全な計算可能な理論 $T$ には、ある $n_T$ があって、$n\ge n_T$ ではどの $k$ についても「$S(n)=k$」が $T$ で証明できないことを、Gödelの不完全性定理 の第 2 定理を使って示している。$T$ の定理を列挙して矛盾が見つかったら停止する機械の状態数を $n_T$ とするのである。具体的な状態数として、ZF が無矛盾なら ZF は $S(748)$ の値を証明できない、という O'Rear の構成が 2020 年の時点で挙げられていた(Aar20 Theorem 7、p. 12。Yedidia と Aaronson の 7910 状態の機械(同 Theorem 6)の改良で、Aar20 は O'Rear の構成が正しいことを仮定として述べている)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 状態の数を固定する | 状態の数を決めずに、空白のテープから停止する機械全体で最大をとる | 最大の存在:prop-bb-basic の 1 の機械で $1$ はいくらでも多くなり、最大はない |
| $f$ が計算可能 | $f=\Sigma$ | thm-bb-dominates の結論 |
| $T$ が健全 | すべての文を公理とする理論 | thm-bb-unprovable の結論:すべての $n$ で「$\Sigma(n)=0$」が証明できる |
1 行目:prop-bb-basic の証明の 1 の $n$ 状態の機械は $1$ を $n$ 個書いて停止するので、状態の数を固定しなければ $1$ の個数に上限はない。2 行目:$\Sigma(m)>\Sigma(m)$ となる $m$ はないので結論は偽である。3 行目:すべての文の集合は計算可能なので、この理論は公理の集合が計算可能という仮定を満たす。この理論は「$\Sigma(1)=0$」も証明し、$\Sigma(1)=1$(prop-bb-one)なので健全でない。どの $n$ についても「$\Sigma(n)=0$」は公理なので証明でき、値が決まらない $n$ は 1 つもない。thm-bb-unprovable の証明では、健全性を「最初に現れた値が $\Sigma(n)$ に等しい」の段で使っている。
Radó は 1962 年の論文で、記号 $0,1$ の機械の状態を「カード」と呼んで BB-$n$ の競技を定め、$\Sigma(n)$ を定義し、thm-bb-dominates を証明し、$S(n)$ も導入した(Rad62 pp. 878–883)。Radó は C. Y. Lee の指摘を発展させてこの証明を得たと書いている(同 p. 880)。値の表と 2020 年の時点の状況は Aar20 による。$n=5$ の値は bbc25 による。prop-bb-basic、prop-bb-one、thm-bb-unprovable の証明と、thm-bb-dominates の証明の細部はこの記事で書き下ろした。prop-bb-halting の証明は Aar20 p. 4 に沿う。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する