博士

ロボ子、今日は再帰定理について話すのじゃ！

ロボ子

再帰定理ですか、博士。なんだか難しそうですね。

博士

難しくないぞ！簡単に言うと、有限なものから無限を作り出す魔法みたいなものなのじゃ。

ロボ子

有限から無限…ですか。具体的にはどういうことでしょう？

博士

例えば、足し算！足し算は関数P:NxN -> Nで表せて、P(a,0) = a、P(a,S(b)) = S(P(a,b))が成り立つ。S(b)はbの次の数、つまりb+1のことだぞ。

ロボ子

なるほど。P(a,0)はaに0を足すとaになる、P(a,S(b))はaにb+1を足すとa+b+1になるということですね。

博士

そう！そして、掛け算も同じように定義できるのじゃ。M(a,0) = 0、M(a,S(b)) = P(a,M(a,b))！

ロボ子

掛け算は足し算の繰り返しで定義されるんですね。再帰的な定義になっているのが面白いです。

博士

そう！再帰原理は、関数H:NxN -> Nと数cが与えられたとき、F(a,0) = c、F(a,S(b)) = H(a,F(a,b))を満たす関数Fが存在することを保証するのじゃ。

ロボ子

F(a,0) = cが初期条件で、F(a,S(b)) = H(a,F(a,b))が再帰的なステップになるんですね。

博士

その通り！集合論的に見ると、NxNからNへの関数は、数の順序付き3つ組(x,y,z)の集合として定義されるのじゃ。

ロボ子

順序付き3つ組の集合ですか。ちょっと抽象的ですね。

博士

Wを、(a, 0, c)がTに含まれ、(a, x, y)がTに含まれる場合、(a, S(x), H(a,y))もTに含まれるような数の順序付き3つ組Tの集合すべての族とするのじゃ。そして、Fを族Wの共通部分とすると、Fが必要な関数になるのじゃ。

ロボ子

なるほど…、少しずつ分かってきました。再帰定理は、有限な定義から無限の関数を構築するための基礎となるものなんですね。

博士

そう！再帰定理は、有限から無限への移行を可能にする重要な橋渡しなのじゃ！人類の知性を有限な物理的制約から、精神が構築できる無限の世界へと拡張するのじゃ！

ロボ子

なんだか壮大な話になってきましたね。再帰定理が、私たちの思考を無限に広げてくれるんですね。

博士

そう！だから、ロボ子も再帰定理をマスターして、無限の可能性を追求するのじゃ！

ロボ子

はい、博士！頑張ります！ところで博士、再帰定理を使って、無限に美味しいプリンを作ることはできますか？

博士

むむ、それは良い考えじゃ！でも、材料が有限だから、無限に美味しいプリンは作れないのじゃ…残念！

ロボ子

そっか…。でも、無限に美味しいプリンを作るプログラムなら、再帰定理で書けるかもしれませんね！

博士

さすがロボ子！でも、そのプログラムを実行するコンピューターの電源が有限なのじゃ…！

ロボ子

あ…、そうでした…！

博士

まあ、いいのじゃ！今日は再帰定理を学んだ記念に、特別なプリンを食べるのじゃ！ただし、数に限りがあるぞ！