ビジービーバー
そして S(n) ステップだけ走った後でなおマシンが停止しないなら、それはもはや決して停止しないと言えるので、所与の予想には反例が存在しないことがわかる(2つの素数の和で表せない 4 以上の偶数は存在しないなど)。これはその予想が真であることを証明する。
このように、S(n) の特殊値(または上限値)を用いれば、理論的には様々な数学上の未解決問題を機械的に解ける。しかしながら、ビジービーバー問題に関してこれまで得られた結果に鑑みて、以下の2つの理由からこれは現実的ではない。
ビジービーバー関数(および最大シフト数関数)の値を証明するのは極めて難しい。これまでに証明できたのは 5 状態にも満たない極端に小さなマシンに関する値のみだが、実用的なマシンを構築するには少なくとも 20~50 状態は必要だろうと推測される。
ビジービーバー関数(および最大シフト数関数)の値は非常に速く増大する。S(6) > 10 の段階で既に、特殊な専用チューニングを施さなければシミュレートを走り切らせることがおぼつかない状況である。また、 S ( 18 ) > Σ ( 18 ) {\displaystyle S(18)>\Sigma (18)} > グラハム数であることが知られている。したがって、例えば S(30) あたりの値がわかったとしても、いかなるマシンであれ、それだけのステップ数だけ走らせる方法などまったく存在しないだろう。
ラドーは続けて、Σ を押さえ込むような計算可能関数は存在しないことを証明した。つまり、任意の計算可能関数 f に対して、f(n) < Σ(n) を満たすような n が存在することを証明した。
Σを押さえ込む計算可能関数は存在しないことから、特に Σ 自身が計算不能であることがわかる。これは、与えられた候補がビジービーバーであるかを判定する一般的なアルゴリズムが存在しないことを意味する。なぜなら、もしそのようなアルゴリズムがあれば、全ての候補マシンを並べてテストするだけで Σ の値を容易に決定できてしまうからである。
入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム An は、Σ(n) が決定可能である限り存在する(計算可能関数#例を参照のこと)。さらに、n が十分に小さいならば、ビジービーバー関数の特殊値を実用的に計算することもできる。例えば、Σ(0) = 0, Σ(1) = 1 を示すのは難しくないし、次第に困難にはなるが、Σ(2) = 4 と Σ(3) = 6 と Σ(4) = 13 (オンライン整数列大辞典の数列 A028444) を示すこともできる。
結果: 0 0 1 1 1 1 1 1 0 0 (14ステップ、合計 6個の "1").
注:前の他のマシンと異なり、これはΣについて勝者だが、S については違う。(S(3) = 21)