原始再帰関数
原始再帰関数(げんしさいきかんすう、英: Primitive Recursive Function)とは、原始再帰と合成で定義される関数であり、再帰関数(計算可能関数)の部分集合である。原始帰納的関数とも。
再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。
数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている(限界の節を参照)。
計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。
原始再帰関数のクラスとは、while文を使用せずに計算できる(すなわちfor文のみで計算可能な)関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。
以下の例と定義の典拠は Kleene (1952) pp. 223-231 である。類似の一覧は Boolos-Burgess-Jeffrey 2002 pp. 63-70 にもある。
以下の例で、原始再帰関数は4種類に分類される:
関数 (Function) - 数論的関数、つまり自然数から自然数への関数
述語 (Predicate) - 自然数から真理値への関数
命題結合子 (Propositional Connective) - 真理値から真理値への関数。ブール関数
表現関数 (Representing Function) - 真理値から自然数への関数。述語の値を 0 や 1 に変換するのは表現関数である。φ の値が 0 か 1 で P が真のとき 0 となるなら、関数 φ(x) は述語 P(x) の表現関数と定義される。
以下の例で、a' のような " ' " 記号付きの記号は後者 (successor) を意味し、一般に "+1" を表す。つまり、a +1 =def a' である。16から21番の関数と #G の関数は原始再帰関数とゲーデル数の数値表現の相互変換に関わるものである。
加算: a+b 乗算: a*b べき乗: a 階乗 a! : 0! = 1, a'! = a!*a' pred(a): デクリメント: 「a の前者」は " a>0 なら a-1 → anew 、そうでなければ 0 → a " と定義される 減算: a ∸ b の定義は " a ≥ b なら a-b, そうでなければ 0 " 最小 (a1, ... an) 最大 (a1, ...