■

授業第十二回目の今回は、最小述語論理上の最小算術Qで、どこまで計算に関する事実（例えば "2+2=4" とか）を証明できるかを、検討したいと思います。

• ステップ1：計算 前回の足し算・かけ算の原始再帰的定義を一般化し、有限ステップで計算が確実に終わることが誰にとっても明白な、計算機で計算可能な関数こと「原始再帰的関数」を定義する
• ステップ2：証明 任意の原始再帰的関数 f(x) と任意の自然数 m,n に関し、f(m)=n になる場合、それがQで証明可能（「数値的表現可能」）かどうかを検討する

今回は、原始再帰的関数の紹介と、数値的表現可能性の最初の部分のみで、実際の対応関係は次回となります。原始再帰的関数は、前回紹介した最小算術における足し算の定義法を一般化した関数で、特徴として有限回でその計算が停止することが明確であることであり、中学･高校の授業に出てくる多くの自然数上の関数をコンピューター上でシミュレートすることができます。