ビジービーバー
ラドーは n-状態ビジービーバー・ゲームには well-defined な「優勝」チューリングマシンが存在することを示した:
n 個の状態と2つの記号を用いるチューリングマシンは有限個しかない(この場合は [4(n+1)] 個)。さらにこのうちの幾つかは停止することが自明である。すなわち、すべての n について、n-状態かつ 2-記号の停止するチューリングマシンが少なくとも一つ存在する。
ビジービーバー関数 Σ(n) は、「状態」 (Turing-instructions) の個数を表す数字 n と空テープが与えられた時に、ビジービーバー・ゲームの「優勝」チューリングマシンが印字する 1 の個数を導く関数として定義される。
前述の性質(二方向の無限長のテープ、5タプルで定義される遷移関数など)を持ち、n-状態かつ2-記号の停止するチューリングマシンの有限で空でない集合を E n {\displaystyle E_{n}} と書く。
チューリングマシン M {\displaystyle M} を空テープから走らせた後で、テープ上に残された 1 の個数を σ ( M ) {\displaystyle \sigma (M)} と書く。
Σ ( 12 ) > 3 ↑↑↑↑ 3 = 3 ↑↑↑ 3 ↑↑↑ 3 = 3 ↑↑↑ 3 ↑↑ 3 3 3 = 3 ↑↑↑ 3 ↑↑ 7 , 625 , 597 , 484 , 987 ≫ 6 ⋅ ( 4096 ↑↑ ) 166 4 ≫ 2 ↑ 4 − 2 ( 4 + 3 ) − 3 = 2 ↑ 2 7 − 3 = 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 − 3 = 2 ↑ 2 ↑ 2 ↑ 2 ↑ 2 ↑ 4 − 3 = 2 2 2 2 2 4 − 3 = 2 2 2 2 16 − 3 = 2 2 2 65536 − 3 {\displaystyle \Sigma (12)>3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 3^{3^{3}}=3\uparrow \uparrow \uparrow 3\uparrow \uparrow 7,625,597,484,987\gg 6\cdot \left(4096\uparrow \uparrow \right)^{166}4\gg 2\uparrow ^{4-2}\left(4+3\right)-3=2\uparrow ^{2}7-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2\uparrow 4-3=2^{2^{2^{2^{2^{4}}}}}-3=2^{2^{2^{2^{16}}}}-3=2^{2^{2^{65536}}}-3}
これに対して、現在知られている Σ(6) の限界値は 10 18267 < 3 3 3 3 = 3 ↑↑ 4 {\displaystyle 10^{18267}<3^{3^{3^{3}}}=3\uparrow \uparrow 4} であり、比較上大変小さい。