原始再帰関数

原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。

再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。

数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（限界の節を参照）。

計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。

原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。

原始再帰関数は数論的関数（定義域と値域が自然数、つまり負でない整数 {0, 1, 2, ...} であるような関数）である。n 個の引数をとる関数を n 項関数 (n-ary：-ary はアリティすなわち引数の個数を意味する) と呼ぶ。基本的な原始再帰関数は以下のような公理で与えられる:

1. 定数関数 (Constant Function) : 0 項の定数関数 0 ^[1]は原始再帰的である。
2. 後者関数（Successor Function）: 1 項 の後者関数 S とは、引数の後者 (successor) を返す関数であり（ペアノの公理）、原始再帰的である。すなわち、S (k) = k + 1.
3. 射影関数（Projection Function）: n ≥ 1 の任意の n について、1 ≤ i ≤ n であるような各 i についての n 項射影関数 P_iⁿ（i 番目の引数を返す関数）は原始再帰的である。

より複雑な原始再帰関数は、以下の公理で与えられる作用素を適用することで得られる:

1. 合成 (Composition) : k 項原始再帰関数 f と k 個の m 項原始再帰関数 g₁, ..., g_k について、f と g₁, ..., g_k の合成関数、すなわち m 項関数 h(x₁, ..., x_m) = f(g₁(x₁, ..., x_m), ..., g_k(x₁, ..., x_m)) は原始再帰的である。
2. 原始再帰法 (Primitive Recursion) : k 項原始再帰関数 f と (k + 2) 項原始再帰関数 g について、f と g の原始再帰として定義される (k + 1) 項関数、すなわち、h(0, x₁, ..., x_k) = f(x₁, ..., x_k) 、 h(S(n), x₁, ..., x_k) = g(h(n, x₁, ..., x_k), n, x₁, ..., x_k) であるような関数 h は原始再帰的である。

上述の基本的な関数と、それに上述の作用素を有限回適用して得られる関数だけが原始再帰的関数である。

射影関数を使って、上述の関数群での引数の個数を変化させることができる。射影関数の合成を行うと、ある関数の引数のサブセットを別の関数に渡すことができる。例えば、2 項原始再帰関数 g と h を次のように合成する。

${\displaystyle f(a,b,c)=g(h(a,c),h(a,b))\!}$

f も原始再帰的である。射影関数による形式的定義は以下のようになる。

${\displaystyle f(a,b,c)=g(h(P_{1}^{3}(a,b,c),P_{3}^{3}(a,b,c)),h(P_{1}^{3}(a,b,c),P_{2}^{3}(a,b,c))}$.

設定によっては、真理値を引数に含む原始再帰関数や値域が真理値であるような原始再帰関数が考えられる (Kleene 1952年、pp.226-227)。これは真理値を何らかの固定された手法で数に変換してやればよい。例えば、「真; true」を 1 に、「偽; false」を 0 に対応させるのが一般的である。このようにすると、集合 A の指示関数（1 または 0 を返す関数）をある数値が集合 A に含まれるかどうかを示す述語とみなすことができる。

引数が 1 つで再帰的に定義される多くの数論的関数は原始再帰的である。基本的な例として加算と「限定された減算」関数がある。

直観的に、加算は次の規則で再帰的に定義できる:

add(0, x) = x,

add(n + 1, x) = add(n, x) + 1.

これを厳密な原始再帰関数の定義に当てはめるため、次のように定義する:

add(0, x) = P₁¹(x),

add(S(n), x) = S(P₁³(add(n, x), n, x)).

ここで、P₁³ は射影関数であり、3つの引数をとり、最初の引数を返す。また、S は後者関数である。

P₁¹ は単純な恒等関数であり、上述の原始再帰関数の定義に当てはめるために導入されている。同語反復的な定義となっていた "+" 記号が無くなっている点に注意されたい。

原始再帰関数は整数ではなく自然数を扱うもので、減算は自然数の範囲では閉じていないため、ここでは限定された減算関数を扱う。限定された減算関数 sub(a, b) は b - a が負でなければその値を返し、負の場合は 0 を返す。

後者関数の反対の動作をする前者関数 (Predecessor Function) を次のように再帰的に定義する:

pred(0)=0,

pred(n + 1) = n.

これを原始再帰関数の形式的定義となるよう変換すると、次のようになる:

pred(0)=0,

pred(S(n)) = P₂²(pred(n), n).

限定された減算関数は、この前者関数を使って定義される。ちょうど後者関数を使って加算が定義されるのと似ている:

sub(0, x) = P₁¹(x),

sub(S(n), x) = pred(P₁³(sub(n, x), n, x)).

ここで sub(a, b) は b - a を表している。原始再帰的定義を単純化するために引数の順番を一般的なものと逆にしている。これは適当な射影の合成で容易に修正できる。

他にも冪乗や素数判定が原始再帰関数である。原始再帰関数 e, f, g, h があるとき、e ≤ f ならば g の値を返し、そうでないとき h の値を返す関数も原始再帰的である。

ゲーデル数を使うと、原始再帰関数を整数や有理数に拡張することができる。整数を標準的な方法でゲーデル数に符号化した場合、その算術演算である加算、減算、乗算は全て原始再帰的である。同様に有理数をゲーデル数で表した場合、体の演算は全て原始再帰的である。

再帰関数は、例えばμ作用素（英語版）を使って定義できる。μ作用素は入力に対して、出力が返ってくることを保証しない。このような関数を部分関数 (Partial Function) と言い、始域のどのような入力に対しても出力が返ってくる関数を全域関数 (Total Function) と言う。

原始再帰関数は全て全域再帰的であるが、全域再帰関数が全て原始再帰的とは言えない。アッカーマン関数 A(m,n) は全域再帰関数でありながら原始再帰的でない有名な例である。アッカーマン関数を使って、原始再帰関数が全域再帰関数の部分集合であるとする見方もある。この場合、関数が原始再帰的であるとは、その関数がチューリングマシンで計算可能で、かつある m に対して A(m, n)以下のステップ数で必ず停止するものと定義される。

原始再帰関数は、計算可能関数とはどのようなものである筈か、という直観と密接に関連する。出発点となる原始再帰関数は（非常に単純なので）直観的に計算可能であり、そこから新たな原始再帰関数を作るための二種類の操作に関しても、具体的に関数値を計算する手続きを与えている。しかし、原始再帰関数の集合に全ての計算可能（全域）関数が含まれるわけではない。（この節の最後に列挙してある具体例を反例として示すことでも証明にはなるが、）カントールの対角線論法を応用して、原始再帰的でない計算可能関数が存在することを証明できる。証明の概略は次の通り:

原始再帰関数の全体は計算的枚挙可能（＝帰納的可算）である。すなわち、2変数の計算可能関数 ${\displaystyle f}$ であって、${\displaystyle f(i,\cdot )(i\in \mathbb {N} )}$ がちょうど原始再帰関数全体と一致するようなものが存在する。この ${\displaystyle f(i,\cdot )}$ を ${\displaystyle f_{i}}$ と書くことにする。原始再帰関数 ${\displaystyle g}$ に対して ${\displaystyle g=f_{i}}$ なる ${\displaystyle i}$ は一意的とは限らない。^[2]。

次のような無限×無限行列を考える。第 ${\displaystyle i}$ 行の第 ${\displaystyle j}$ 列には ${\displaystyle f_{i}(j)}$ の値が書かれているものとする。この行列の対角線部分に注目する。

関数 ${\displaystyle g(x):=f_{x}(x)+1}$ を考える。${\displaystyle g}$ は上記の行列の対角線上の値に 1 を加えた値を返す関数である。この関数は計算可能だが、如何なる原始再帰関数もこの関数を計算できないことが明らかである。何故ならどのような原始再帰関数も、この関数とは対角線部分において値が異なるからである。従って原始再帰的でない計算可能関数が存在する。

この論法は枚挙可能な（全域）計算可能関数の任意のクラスに適用できる。別記事 (en) を参照のこと。ただし、部分計算可能関数は、例えばチューリングマシンでの符号化を使って番号付けするなどの方法で、明確に枚挙可能である。

全域再帰的だが原始再帰的でない関数として、他にも次のような例が知られている:

• アッカーマン関数 ${\displaystyle A(x,y)}$ や2つの引数に同じ値を与えた関数 ${\displaystyle A(x,x)}$ は全域再帰的だが原始再帰的ではない。
• クヌースの矢印記法は全域再帰的だが原始再帰的でない。アッカーマン関数はクヌースの矢印記法による表示を持つ。
• グジェゴルチク階層の初期関数 ${\displaystyle E_{i}(x)}$ は2変数関数として全域再帰的だが原始再帰的ではない。
• パリス・ハリントンの定理は、原始再帰的でない全域再帰関数に関わる。この関数はラムゼー理論に基づいているため、アッカーマン関数よりも「自然」だと言われることがある。
• スーダン関数
• グッドスタイン関数（英語版）

以下の例と定義の典拠は Kleene (1952) pp. 223-231 である。類似の一覧は Boolos-Burgess-Jeffrey 2002 pp. 63-70 にもある。

以下の例で、原始再帰関数は4種類に分類される:

1. 関数 (Function) - 数論的関数、つまり自然数から自然数への関数
2. 述語 (Predicate) - 自然数から真理値への関数
3. 命題結合子 (Propositional Connective) - 真理値から真理値への関数。ブール関数
4. 表現関数 (Representing Function) - 真理値から自然数への関数。述語の値を 0 や 1 に変換するのは表現関数である。φ の値が 0 か 1 で P が真のとき 0 となるなら、関数 φ(x) は述語 P(x) の表現関数と定義される。

以下の例で、a' のような " ' " 記号付きの記号は後者 (successor) を意味し、一般に "+1" を表す。つまり、a +1 =_def a' である。16から21番の関数と #G の関数は原始再帰関数とゲーデル数の数値表現の相互変換に関わるものである。

1. 加算: a+b
2. 乗算: a*b
3. べき乗: a^b,
4. 階乗 a! : 0! = 1, a'! = a!*a'
5. pred(a): デクリメント: 「a の前者」は " a>0 なら a-1 → a_new 、そうでなければ 0 → a " と定義される
6. 減算: a ∸ b の定義は " a ≥ b なら a-b, そうでなければ 0 "
7. 最小 (a₁, ... a_n)
8. 最大 (a₁, ... a_n)
9. 絶対値: | a-b | =_def a ∸ b + b ∸ a
10. ~sg(a): NOT[signum(a}]: a=0 なら sg(a)=1 、そうでなく a>0 なら sg(a)=0
11. sg(a): signum(a): a=0 なら sg(a)=0 そうでなく a>0 なら sg(a)=1
12. 剰余 (a, b): a が b で割り切れない場合の余り
13. 除算 [ a | b ]: 剰余が 0 の場合。
14. s = b: sg | a - b |
15. a < b: sg( a' ∸ b )
16. a | b: 除算
17. Pr(a): a は素数 Pr(a) =_def a>1 & NOT(Exists c)_1<c<a [ c|a ]
18. P_i: i+1 番目の素数
19. (a)_i : p_i =_def μx [ _x<a [p_i^x|a & NOT(p_i ^x'|a ] の指数 a_i 。μx は #E で説明されている最小化演算子。
20. lh(a): a の「長さ」または消えない指数 (non-vanishing exponents) の個数
21. a*b: a と b が素因数であるとき、a*b は素因数の乗算結果を示す。
22. lo(x, y): 基数 y での x の対数

以下では、x =_def x_i, ... x_n という省略形を使用。添え字も必要に応じて使われる。「x において原始再帰的」とは「x が原始再帰的な場合は原始再帰的である」という意味。

• #A: 関数 Ψ と定数 q₁ , ... q_n から明示的に定義できる関数 φ は Ψ において原始再帰的である。
• #B: 総和 Σ_y<z ψ(x, y) と総乗 Π_y<zψ(x, y) は ψ において原始再帰的である。
• #C: 述語 Q の各引数を関数 χ₁ , ..., χ_m で置き換えた述語 P は χ₁, ..., χ_m, Q において原始再帰的である。
• #D: 以下の述語は Q と R において原始再帰的である:

• 否定: NOT_Q(x) .
• 論理和: Q(x) V R(x),
• 論理積: Q(x) & R(x),
• 含意: Q(x) → R(x)
• 同値: Q(x) ≡ R(x)

• #E: 以下の述語は、述語 R において原始再帰的である:

• (Ey)_y<z R(x, y): (Ey)_y<z とは、「ある z よりも小さい y が存在し、～が成り立つ」という意味
• (y)_y<z R(x, y): (y) とは、「z よりも小さい全ての y について ～ が成り立つ」という意味
• μy_y<z R(x, y): 演算子 μy_y<z R(x, y) は最小化演算子あるいはμ演算子の限定された形式である。その定義は「z より小さい最小の y について R(x, y) が真である」ことを意味する。

• #F: ケースによる定義: Q₁, ..., Q_m は相互排他的述語であるとき、φ₁, ..., Q₁, ... Q_m において以下の関数は原始再帰的である:

φ(x) =

• φ₁(x) if Q₁(x) is true,
• . . . . . . . . . . . . . . . . . . .
• φ_m(x) if Q_m(x) is true
• φ_m+1(x) otherwise

• #G: φ が方程式 φ(y, x) = χ(y, NOT-φ(y; x₂, ... x_n ), x₂, ... x_n を満足するとき χ において φ は原始再帰的である。

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7
• Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57
• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.

• 再帰的定義
• PR
• μ再帰関数

1. ^ つまり、0 項関数とは自然数のことであると取り決める。
2. ^ ただし原始帰納的関数を重複なく枚挙する計算可能関数が存在することが知られている。Shih-Chao Liu, An enumeration of the primitive recursive functions without repetation, Tohoku Math. J. (2) Volume 12, Number 3 (1960), pp. 400-402.

• 再帰的関数論 照井一成（京都大学数理解析研究所）