原始再帰関数
原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。
再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。
数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（限界の節を参照）。
原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。
定義
原始再帰関数は数論的関数（定義域と値域が自然数、つまり負でない整数 {0, 1, 2, ...} であるような関数）である。n 個の引数をとる関数を n 項関数 (n-ary：-ary はアリティすなわち引数の個数を意味する) と呼ぶ。基本的な原始再帰関数は以下のような公理で与えられる:
- 定数関数 (Constant Function) : 0 項の定数関数 0 [1]は原始再帰的である。
- 後者関数（Successor Function）: 1 項 の後者関数 S とは、引数の後者 (successor) を返す関数であり（ペアノの公理）、原始再帰的である。すなわち、S (k) = k + 1.
- 射影関数（Projection Function）: n ≥ 1 の任意の n について、1 ≤ i ≤ n であるような各 i についての n 項射影関数 Pin（i 番目の引数を返す関数）は原始再帰的である。
より複雑な原始再帰関数は、以下の公理で与えられる作用素を適用することで得られる:
- 合成 (Composition) : k 項原始再帰関数 f と k 個の m 項原始再帰関数 g1, ..., gk について、f と g1, ..., gk の合成関数、すなわち m 項関数 h(x1, ..., xm) = f(g1(x1, ..., xm), ..., gk(x1, ..., xm)) は原始再帰的である。
- 原始再帰法 (Primitive Recursion) : k 項原始再帰関数 f と (k + 2) 項原始再帰関数 g について、f と g の原始再帰として定義される (k + 1) 項関数、すなわち、h(0, x1, ..., xk) = f(x1, ..., xk) 、 h(S(n), x1, ..., xk) = g(h(n, x1, ..., xk), n, x1, ..., xk) であるような関数 h は原始再帰的である。
上述の基本的な関数と、それに上述の作用素を有限回適用して得られる関数だけが原始再帰的関数である。
射影関数の役割
射影関数を使って、上述の関数群での引数の個数を変化させることができる。射影関数の合成を行うと、ある関数の引数のサブセットを別の関数に渡すことができる。例えば、2 項原始再帰関数 g と h を次のように合成する。
- 原始再帰関数のページへのリンク
