ビジービーバー
S(n) が計算可能関数であると仮定し、S(n) を求めるチューリングマシンを EvalS と呼ぼう。このマシンは 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 に達したならば停止する)。n0 と n0 の和 (n0 + n0) を N と書こう。
ここで今度は BadS という名の複合マシンを用意し、この内容は Create_n0 | Double | EvalS | Clean とする。
このマシンは N 状態を持つことに注意する。空テープから処理を開始し、まず n0 個の一連の 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) もまた計算不能であることが従う。
結果: 0 0 1 0 0 (1 ステップ、合計 1個の "1")
n が十分に大きい場合、S(n) は単に計算不能であるだけでなく、ある種の公理系の下では決定不能である。
2016年、Yedidia と Aaronson は 7910-状態の、ZF と、幾つかの追加公理である stationary Ramsey property (SRP) とで構成される公理系が矛盾する場合のみ停止するチューリングマシンを明示的に作成し、ゲーデルの不完全性定理により ZF+SRP の下では S(7910) の値が決定不能であることを証明した。 後に結果は改良され、同年 O’Rear は SRP に依存せず、ZF (厳密には ZF よりわずかに弱いが、無矛盾性が ZF および ZFC と一致する公理系) が矛盾する場合にのみ停止する 1919-状態のチューリングマシンを作成して、ZF の下では S(1919) の値が証明できないことを示した。 状態数は翌年 O’Rear 自身によって 748-状態に、2023年 には Riebel により 745-状態にまで改善された。
つまり 745 以上の n と、一般的な数学の基礎となる公理系である ZFC の下において、S(n) の値は決定不能である。
ビジービーバー関数はやり応えのある数学ゲームというだけでなく、深遠な応用を持つ。十分大きな n について S(n) の値が得られれば、それを用いて数多の数学上の未解決問題を機械的に解くことができる。
数学上の予想の中で、可算無限個のケースの中から反例を見つけ出せればその予想の否定を証明できるようなものを考える(例えばゴールドバッハ予想などが該当)。それらの予想について値を増分しながらテストするようなコンピュータプログラムを書く(ゴールドバッハ予想なら、4 以上の偶数全てについて、2つの素数の和として表せるかを順次調べる)。このプログラムを n-状態チューリングマシンでシミュレートする(もしくは、well-definedなプログラム言語であればその言語版のビジービーバー関数を定義できるので、そちらで代替してもよい)。もし反例(先の例で言えば、2つの素数の和で表せない偶数)を見付けたならば、停止して結果を表示する。反例が見付からなければプログラムは永遠に走り続ける(このプログラムは反例を見つけた場合にしか停止しないものとする)。
さて、今このプログラムは n-状態チューリングマシンでシミュレートしているので、もし S(n) がわかるなら、単にそのステップ数だけそのプログラムを走らせれば、そのプログラムが停止するのかどうかが(有限の時間内で)判明する。