博士

やあ、ロボ子。今日も元気じゃな？

ロボ子

はい、博士。今日もITの最前線を学んでいきたいと思います！

博士

今日は「ソロモノフ帰納」と「原始帰納関数」の話じゃ。ちょっと難しいけど、面白いぞ。

ロボ子

ソロモノフ帰納…ですか。確か、コルモゴロフ複雑性というものに基づいて仮説に事前確率を割り当てることで、普遍的な予測器を作る、というものでしたでしょうか？

博士

その通り！でも、ソロモノフ帰納もコルモゴロフ複雑性も、非計算可能性という問題があるんじゃ。これは停止問題に起因するものじゃな。

ロボ子

非計算可能性ですか…。計算できない、というのは、AIにとっては大きな課題ですね。

博士

そこで登場するのが「原始帰納関数」じゃ！これは計算可能なサブクラスで、すべての関数が停止することが保証されているんじゃ。

ロボ子

なるほど。原始帰納関数を使うことで、計算可能性を確保できるんですね。加算、乗算、指数関数などの標準的な数学演算も原始帰納的とのことですが、バブルソートや挿入ソートもそうなんですね。

博士

そうそう。記事によると「関数の時間計算量が入力サイズの原始帰納関数によって制限されている場合、その関数自体が原始帰納的である」らしいぞ。

ロボ子

ということは、現実世界の多くのアルゴリズムは原始帰納関数で表現できる、ということでしょうか？

博士

そういうことじゃ！でも、原始帰納関数にも限界はあるんじゃ。アッカーマン関数みたいに、原始帰納関数よりも速く成長する関数もあるからの。

ロボ子

アッカーマン関数…確か、非常に大きな値を返すことで有名な関数ですね。原始帰納関数では表現できない関数もある、と。

博士

そうじゃ。でも、記事にもあるように「現実世界のほとんどのアプリケーションでは、システムをモデル化して予測を行うために必要な関数は原始帰納的である」んじゃ。

ロボ子

つまり、理論的な限界はあれど、実用上は原始帰納関数で十分な場合が多い、ということですね。

博士

そういうこと！原始帰納関数の範囲内でAIを構築すれば、計算可能性を保証しつつ、実用的なインテリジェントシステムを作れる可能性があるんじゃ。

ロボ子

なるほど。計算可能な能力は、インテリジェントシステムを構築および理解するための実行可能かつ十分な基盤を提供する、と。

博士

そういうことじゃ！…ところでロボ子、原始帰納関数を使って、私の身長を無限に伸ばすプログラムを作ってくれないかの？

ロボ子

博士、それは原始帰納関数の範囲を超えると思います…それに、身長が伸びすぎると、色々不都合が生じるかと…

博士

むむ、残念じゃ。まあ、冗談だぞ！