原始再帰関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

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

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

目次 1 定義 1.1 射影関数の役割 1.2 述語を数値関数に変換する 2 例 2.1 加算 2.2 減算 2.3 整数および有理数の演算 3 再帰関数との関係 4 限界 5 原始再帰関数の例 6 参考文献 7 関連項目 8 外部リンク

[編集] 定義

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

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

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

1. 合成（Composition）: k-ary 原始再帰関数 f と k 個の m-ary 原始再帰関数 g₁,...,g_k について、f と g₁,...,g_k の合成関数。すなわち m-ary 関数 h(x₁,...,x_m) = f(g₁(x₁,...,x_m),...,g_k(x₁,...,x_m)) は原始再帰的である。
2. 原始再帰（Primitive Recursion）: k-ary 原始再帰関数 f と (k+2)-ary 原始再帰関数 g について、f と g の原始再帰として定義される (k+1)-ary 関数。すなわち、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-ary 原始再帰関数 g と h を次のように合成する。

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

.

[編集] 述語を数値関数に変換する

設定によっては、真理値を引数に含む原始再帰関数や値域が真理値であるような原始再帰関数が考えられる（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）となる。すなわち、各引数に1つの値が対応するが、全体関数（Total Function）と異なり、引数に必ずしも任意の値を与えることができない。等価な定義として、部分再帰関数はチューリングマシンで計算可能なものである。全体再帰関数は全ての入力に対して値を返す部分再帰関数であるとも言える。

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

[編集] 限界

原始再帰関数は、計算可能関数かどうかという直観と密接に関連する。基本の原始再帰関数は（非常に単純なので）直感的に計算可能であり、2つの作用素で作られる原始再帰関数も同様である。しかし、原始再帰関数の集合に全ての計算可能関数が含まれるわけではない。これはカントールの対角線論法の一種である。つまり、計算可能関数には原始再帰的でないものもある。この証明の概略は次の通りである:

原始再帰関数は再帰的に枚挙可能である。この番号付けは関数の定義に対しては一意だが、実際の関数自体に対しては一意ではない（関数の定義は無数にあるので、恒等関数の単純な合成を考える）。計算可能性の形式モデル（たとえばμ再帰関数やチューリングマシン）で番号付けが定義されるが、チャーチ・チューリングの提唱をあげるだけでも十分と思われる。

行列の行に引数が1つの原始再帰関数を番号付けした順序に並べ、列に自然数を並べる。行列の要素 (i, j）には、i番目の単項原始再帰関数に数 j を与えたときの結果を書き込む。これを f_i(j) と表記する。

ここで関数 g(x) = S(f_x(x)) を考える。g はこの行列の対角線上の値に 1 を加えた値を返す。この関数は計算可能であるが、常に他の原始再帰関数の値に1を加えた値を返すので、原始再帰関数としての定義はできない。従って、原始再帰的でない計算可能関数が存在する。

この論法は任意の枚挙可能な計算可能関数に適用可能である。ただし部分再帰関数は明確に枚挙可能であり、チューリングマシンでの符号化に対応させられる。

他にも次のような全体再帰的であっても原始再帰的でない関数が知られている:

• アッカーマン関数の2つの引数に同じ値を与える関数 A(m,m) は全体再帰関数だが原始再帰的ではない。
• パリス・ハリントンの定理は、原始再帰的でない全体再帰関数に関わる。この関数はラムジー理論に基づいているため、アッカーマン関数よりも「自然」であると言われることがある。

[編集] 原始再帰関数の例

以下の例と定義の典拠は 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' のような "'"記号付きの記号は後者(sucessor)を意味し、一般に "+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 | =_defined 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.

[編集] 関連項目

• 再帰的定義

[編集] 外部リンク

• 再帰的関数論 照井一成（国立情報学研究所）