ビジービーバーQ&A: 計算不可能の鳥瞰図

　昨今いかがお過ごしでしょうか。こちらは、ほんとビジーなので、無限に時間が欲しいと毎日天に祈っています。

　ビジーといえば、ところで、ビジービーバー関数と呼ばれる関数をご存知でしょうか。自然数上で定義された、大体こんなかんじの関数です。

\[BB(n)=1+\sum_{i=0}^{n}\lim_{s\to\infty}\psi(i,n,s).\]

　この $ \psi $ については、あとで説明しますが、 $ \psi $ は具体的な原始再帰関数で、 $ s\to\infty $ での極限はちゃんと収束します。なので、当然ながら、 $ BB $ も自然数上の well-defined な全域関数です。というか、仮に $ \psi $ が具体的に何かということを知らなくても、上に書いたような極限がしっかり収束するような自然数上の関数 $ \psi $ であれば何であろうとも、上の定義が well-defined な自然数上の全域関数を与えるということは（よほどラディカルな思想をお持ちでない限り）誰しも認めるところでしょう。まあつまりは、ビジービーバー関数とは、よくある標準的な数学的関数です。むしろ、具体的な原始再帰関数から作られている分、数学に出てくるほとんどの関数よりも遥かに地に足の着いた定義ですね。

　さて、そういうわけで今日は、計算不可能性に関する正しい勘を身につけよう、のコーナーです。

▼目次

1. ビジービーバー関数とはなにか
2. 急増加階層とゲーデルの夢
3. 急増加階層におけるビジービーバー関数
4. 無限の彼方へ
5. ジャンプ、ハイパージャンプ、スーパージャンプ
6. 無限ゲームの決定性
7. 再帰的マーロ順序数を越えて
8. 無限時間チューリングマシン
9. 年表とまとめ