原始再帰関数

原始再帰関数（げんしさいきかんすう、）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。
再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。
数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、"n" 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（限界の節を参照）。
計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。
原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。
定義.
原始再帰関数は数論的関数（定義域と値域が自然数、つまり負でない整数 {0, 1, 2, ...} であるような関数）である。"n" 個の引数をとる関数を "n" 項関数 ("n"-ary：-ary はアリティすなわち引数の個数を意味する) と呼ぶ。基本的な原始再帰関数は以下のような公理で与えられる:
より複雑な原始再帰関数は、以下の公理で与えられる作用素を適用することで得られる:
上述の基本的な関数と、それに上述の作用素を有限回適用して得られる関数だけが原始再帰的関数である。
射影関数の役割.
射影関数を使って、上述の関数群での引数の個数を変化させることができる。射影関数の合成を行うと、ある関数の引数のサブセットを別の関数に渡すことができる。例えば、2 項原始再帰関数 "g" と "h" を次のように合成する。
"f" も原始再帰的である。射影関数による形式的定義は以下のようになる。
述語を数値関数に変換する.
設定によっては、真理値を引数に含む原始再帰関数や値域が真理値であるような原始再帰関数が考えられる (Kleene 1952年、pp.226-227)。これは真理値を何らかの固定された手法で数に変換してやればよい。例えば、「真; true」を "1" に、「偽; false」を "0" に対応させるのが一般的である。このようにすると、集合 "A" の指示関数（"1" または "0" を返す関数）をある数値が集合 "A" に含まれるかどうかを示す述語とみなすことができる。
例.
引数が 1 つで再帰的に定義される多くの数論的関数は原始再帰的である。基本的な例として加算と「限定された減算」関数がある。
加算.
直観的に、加算は次の規則で再帰的に定義できる:
これを厳密な原始再帰関数の定義に当てはめるため、次のように定義する:
ここで、"P"13 は射影関数であり、3つの引数をとり、最初の引数を返す。また、"S" は後者関数である。
"P"11 は単純な恒等関数であり、上述の原始再帰関数の定義に当てはめるために導入されている。同語反復的な定義となっていた "+" 記号が無くなっている点に注意されたい。
減算.
原始再帰関数は整数ではなく自然数を扱うもので、減算は自然数の範囲では閉じていないため、ここでは限定された減算関数を扱う。限定された減算関数 sub("a", "b") は "b" - "a" が負でなければその値を返し、負の場合は "0" を返す。
後者関数の反対の動作をする前者関数 (Predecessor Function) を次のように再帰的に定義する:
これを原始再帰関数の形式的定義となるよう変換すると、次のようになる:
限定された減算関数は、この前者関数を使って定義される。ちょうど後者関数を使って加算が定義されるのと似ている:
ここで sub("a", "b") は "b" - "a" を表している。原始再帰的定義を単純化するために引数の順番を一般的なものと逆にしている。これは適当な射影の合成で容易に修正できる。
他にも冪乗や素数判定が原始再帰関数である。原始再帰関数 "e", "f", "g", "h" があるとき、"e" ≤ "f" ならば "g" の値を返し、そうでないとき "h" の値を返す関数も原始再帰的である。
整数および有理数の演算.
ゲーデル数を使うと、原始再帰関数を整数や有理数に拡張することができる。整数を標準的な方法でゲーデル数に符号化した場合、その算術演算である加算、減算、乗算は全て原始再帰的である。同様に有理数をゲーデル数で表した場合、体の演算は全て原始再帰的である。
再帰関数との関係.
再帰関数は、例えばを使って定義できる。μ作用素は入力に対して、出力が返ってくることを保証しない。このような関数を部分関数 (Partial Function) と言い、始域のどのような入力に対しても出力が返ってくる関数を全域関数 (Total Function) と言う。
原始再帰関数は全て全域再帰的であるが、全域再帰関数が全て原始再帰的とは言えない。アッカーマン関数 "A"("m","n") は全域再帰関数でありながら原始再帰的でない有名な例である。アッカーマン関数を使って、原始再帰関数が全域再帰関数の部分集合であるとする見方もある。この場合、関数が原始再帰的であるとは、その関数がチューリングマシンで計算可能で、かつある "m" に対して "A"("m", "n")以下のステップ数で必ず停止するものと定義される。
限界.
原始再帰関数は、計算可能関数とはどのようなものである筈か、という直観と密接に関連する。出発点となる原始再帰関数は（非常に単純なので）直観的に計算可能であり、そこから新たな原始再帰関数を作るための二種類の操作に関しても、具体的に関数値を計算する手続きを与えている。しかし、原始再帰関数の集合に全ての計算可能（全域）関数が含まれるわけではない。（この節の最後に列挙してある具体例を反例として示すことでも証明にはなるが、）カントールの対角線論法を応用して、原始再帰的でない計算可能関数が存在することを証明できる。証明の概略は次の通り:
この論法は枚挙可能な（全域）計算可能関数の任意のクラスに適用できる。別記事 () を参照のこと。ただし、部分計算可能関数は、例えばチューリングマシンでの符号化を使って番号付けするなどの方法で、明確に枚挙可能である。
全域再帰的だが原始再帰的でない関数として、他にも次のような例が知られている:
原始再帰関数の例.
以下の例で、原始再帰関数は4種類に分類される:
以下の例で、a' のような " ' " 記号付きの記号は後者 (successor) を意味し、一般に "+1" を表す。つまり、a +1 =def a' である。16から21番の関数と #G の関数は原始再帰関数とゲーデル数の数値表現の相互変換に関わるものである。