授業第十回目の今回は、最小述語論理上の最小算術Qで、どこまで計算に関する事実を証明できるかを、検討したいと思います。
- ステップ1:前回の足し算の原始再帰的定義を一般化し、有限ステップで計算が確実に終わる関数こと「原始再帰的関数」のクラスを定義する
- ステップ2:任意の原始再帰的関数 f(x) と任意の自然数 m,n に関し、f(m)=n になる場合、それがQで証明可能(「数値的表現可能」)かどうかを検討する
今回は時間がないので、原始再帰的関数の紹介と、数値的表現可能性の最初の部分のみで、実際の対応関係は次回となります。