ソフトウェア基礎理論 5.5 帰納的関数論f,g を原始帰納的関数とするとき、 h(x1 ... xn, 0) = f(x1 ... xn) h(x1 ... xn, y+1) = g(f(x1 ... xn), y, h(x1 ... xn, y)) によって定義される h この演算がちゃんと停止する（無限ループにならず、一定の時間内に計算が行える）かどうかを調べます。上の 3 つは瞬間的に答えが出そうです。関数合成は、f1, f2 ... ,g が計算できるなら、結果が出ます。最後の一つは、計算を行う毎に h() の最後の引数の数字が一つずつ小さくなっていくので、そのうち 0 になり、停止します。よって、この 5 つの組み合わせでは、必ず計算結果が出ます。 原始(帰納的)関数の例 この世の中にあるほとんどの計算は、原始帰納的関数で定義できます。ここでは自然数範囲での演算を示します。 関数例 定数関数
