原始的な再帰関数

（ベクトル値）関数^{[ 5 ]}${\displaystyle f:\mathbb {N} ^{m}\to \mathbb {N} ^{n}}$プリミティブ再帰とは、次のように書ける場合を指します。

${\displaystyle f(x_{1},\dots ,x_{m})=(f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}))}$

各コンポーネント${\displaystyle f_{i}:\mathbb {N} ^{m}\to \mathbb {N} }$は（スカラー値の）原始的な再帰関数です。^{[ 6 ]}

2項関数の定義${\displaystyle \operatorname {追加} }$引数の合計を計算するには、基本再帰演算子を使用して取得できます。${\displaystyle \rho }$この目的のために、よく知られた方程式

${\displaystyle {\begin{aligned}0+y&=y,\\S(x)+y&=S(x+y)\end{aligned}}}$

「原始再帰関数用語で言い換えられる」: 定義において${\displaystyle \rho (g,h)}$最初の式は、選択することを示唆している。${\displaystyle g=P_{1}^{1}}$取得する${\displaystyle \operatorname {追加} (0,y)=g(y)=y}$2番目の式は選択することを示唆している${\displaystyle h=S\circ P_{2}^{3}}$取得する${\displaystyle \operatorname {Add} (S(x),y)=h(x,\operatorname {Add} (x,y),y)=(S\circ P_{2}^{3})(x,\operatorname {Add} (x,y),y)=S(\operatorname {Add} (x,y))}$したがって、加算関数は次のように定義できます。${\displaystyle \operatorname {Add} =\rho (P_{1}^{1},S\circ P_{2}^{3})}$計算例として、

${\displaystyle {\begin{aligned}\operatorname {Add} (1,7)&=\rho (P_{1}^{1},S\circ P_{2}^{3})(S(0),7)&&{\text{ by Def. }}\operatorname {Add} ,S\\&=(S\circ P_{2}^{3})(0,\operatorname {Add} (0,7),7)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=S(\operatorname {Add} (0,7))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=S(\rho (P_{1}^{1},S\circ P_{2}^{3})(0,7))&&{\text{ by Def. }}\operatorname {Add} \\&=S(P_{1}^{1}(7))&&{\text{ by case }}\rho (g,h)(0,...)\\&=S(7)&&{\text{ by Def. }}P_{1}^{1}\\&=8&&{\text{ by Def. }}S.\\\end{aligned}}}$

与えられた${\displaystyle \operatorname {Add} }$1項関数${\displaystyle \operatorname {Add} \circ (P_{1}^{1},P_{1}^{1})}$その主張を倍増させる、${\displaystyle (\operatorname {Add} \circ (P_{1}^{1},P_{1}^{1}))(x)=\operatorname {Add} (x,x)=x+x.}$

足し算と同様に、掛け算は次のように定義できます。${\displaystyle \operatorname {Mul} =\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))}$これは、よく知られている乗算の式を再現するものです。

${\displaystyle {\begin{aligned}\operatorname {Mul} (0,y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(0,y)&&{\text{ by Def. }}\operatorname {Mul} \\&=C_{0}^{1}(y)&&{\text{ by case }}\rho (g,h)(0,...)\\&=0&&{\text{ by Def. }}C_{0}^{1}.\end{aligned}}}$

そして

${\displaystyle {\begin{aligned}\operatorname {Mul} (S(x),y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(S(x),y)&&{\text{ by Def. }}\operatorname {Mul} \\&=(\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(x,\operatorname {Mul} (x,y),y)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Add} (\operatorname {Mul} (x,y),y)&&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\&=\operatorname {Mul} (x,y)+y&&{\text{ by property of }}\operatorname {Add} .\end{aligned}}}$

前任関数は後任関数の「反対」として機能し、規則によって再帰的に定義されます。${\displaystyle \operatorname {Pred} (0)=0}$そして${\displaystyle \operatorname {Pred} (S(n))=n}$原始的な再帰的定義は${\displaystyle \operatorname {Pred} =\rho (C_{0}^{0},P_{1}^{2})}$計算例として、

${\displaystyle {\begin{aligned}\operatorname {Pred} (8)&=\rho (C_{0}^{0},P_{1}^{2})(S(7))&&{\text{ by Def. }}\operatorname {Pred} ,S\\&=P_{1}^{2}(7,\operatorname {Pred} (7))&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=7&&{\text{ by Def. }}P_{1}^{2}.\end{aligned}}}$

限定減算関数（「monus」とも呼ばれ、「${\displaystyle \mathbin {\dot {-}} }$）は前任関数から定義可能です。それは以下の式を満たします。

${\displaystyle {\begin{aligned}y\mathbin {\dot {-}} 0&=y,\\y\mathbin {\dot {-}} S(x)&=\operatorname {Pred} (y\mathbin {\dot {-}} x).\end{aligned}}}$

再帰は2番目の引数に対して実行されるため、まず逆引き算の原始的な再帰的定義から始めます。${\displaystyle \operatorname {RSub} (y,x)=x\mathbin {\dot {-}} y}$。その再帰は最初の引数に対して実行されるため、加算と同様に、その原始的な再帰定義が得られます。${\displaystyle \operatorname {RSub} =\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})}$逆順の引数を取り除くには、次のように定義します。${\displaystyle \operatorname {Sub} =\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2})}$計算例として、

${\displaystyle {\begin{aligned}\operatorname {Sub} (8,1)&=(\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2}))(8,1)&&{\text{ by Def. }}\operatorname {Sub} \\&=\operatorname {RSub} (1,8)&&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\&=\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(S(0),8)&&{\text{ by Def. }}\operatorname {RSub} ,S\\&=(\operatorname {Pred} \circ P_{2}^{3})(0,\operatorname {RSub} (0,8),8)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Pred} (\operatorname {RSub} (0,8))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=\operatorname {Pred} (\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(0,8))&&{\text{ by Def. }}\operatorname {RSub} \\&=\operatorname {Pred} (P_{1}^{1}(8))&&{\text{ by case }}\rho (g,h)(0,...)\\&=\operatorname {Pred} (8)&&{\text{ by Def. }}P_{1}^{1}\\&=7&&{\text{ by property of }}\operatorname {Pred} .\end{aligned}}}$

場合によっては、数値と真偽値を混ぜたタプルを入力として受け取る原始的な再帰関数を考えるのが自然です（つまり、${\displaystyle t}$確かに、そして${\displaystyle f}$（偽の場合）または真偽値を出力として生成する。^{[ 8 ]}これは、任意の固定された方法で真偽値を数値で識別することによって実現できます。たとえば、真偽値を識別して、${\displaystyle t}$番号付き${\displaystyle 1}$、そして真理値${\displaystyle f}$番号付き${\displaystyle 0}$この識別が行われた後は、集合の特性関数は${\displaystyle A}$これは常に返される${\displaystyle 1}$または${\displaystyle 0}$は、数値が集合に含まれているかどうかを示す述語と見なすことができる。${\displaystyle A}$本稿の残りの部分では、述語と数値関数のこのような同一視を前提とする。

原始的な再帰述語の例として、1項関数${\displaystyle \operatorname {IsZero} }$は次のように定義されるものとする。${\displaystyle \operatorname {IsZero} (x)=1}$もし${\displaystyle x=0}$、 そして${\displaystyle \operatorname {IsZero} (x)=0}$それ以外の場合は、定義することで実現できます。${\displaystyle \operatorname {IsZero} =\rho (C_{1}^{0},C_{0}^{2})}$。 それから${\displaystyle \operatorname {IsZero} (0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}()=1}$例えば${\displaystyle \operatorname {IsZero} (8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,\operatorname {IsZero} (7))=0}$。

プロパティを使用する${\displaystyle x\leq y\iff x\mathbin {\dot {-}} y=0}$2項関数${\displaystyle \operatorname {Leq} }$定義できる${\displaystyle \operatorname {Leq} =\operatorname {IsZero} \circ \operatorname {Sub} }$。 それから${\displaystyle \operatorname {Leq} (x,y)=1}$もし${\displaystyle x\leq y}$、 そして${\displaystyle \operatorname {Leq} (x,y)=0}$それ以外の場合。計算例として、

${\displaystyle {\begin{aligned}\operatorname {Leq} (8,3)&=\operatorname {IsZero} (\operatorname {Sub} (8,3))&&{\text{ by Def. }}\operatorname {Leq} \\&=\operatorname {IsZero} (5)&&{\text{ by property of }}\operatorname {Sub} \\&=0&&{\text{ by property of }}\operatorname {IsZero} \\\end{aligned}}}$

かつて定義${\displaystyle \operatorname {Leq} }$が得られたので、逆述語は次のように定義できる。${\displaystyle \operatorname {Geq} =\operatorname {Leq} \circ (P_{2}^{2},P_{1}^{2})}$。 それから、${\displaystyle \operatorname {Geq} (x,y)=\operatorname {Leq} (y,x)}$が真である（より正確には、値が 1 である）のは、次の場合に限る。${\displaystyle x\geq y}$。

プログラミング言語でおなじみの3項if-then-else演算子は次のように定義できます。${\displaystyle \operatorname {If} =\rho (P_{2}^{2},P_{3}^{4})}$。次に、任意の${\displaystyle x}$、

${\displaystyle {\begin{aligned}\operatorname {If} (S(x),y,z)&=\rho (P_{2}^{2},P_{3}^{4})(S(x),y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{3}^{4}(x,\operatorname {If} (x,y,z),y,z)&&{\text{ by case }}\rho (S(...),...)\\&=y&&{\text{ by Def. }}P_{3}^{4}\end{aligned}}}$

そして

${\displaystyle {\begin{aligned}\operatorname {If} (0,y,z)&=\rho (P_{2}^{2},P_{3}^{4})(0,y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{2}^{2}(y,z)&&{\text{ by case }}\rho (0,...)\\&=z&&{\text{ by Def. }}P_{2}^{2}.\end{aligned}}}$

つまり、${\displaystyle \operatorname {If} (x,y,z)}$then 部分を返します (${\displaystyle y}$) if 部分 (${\displaystyle x}$) は真であり、else 部分 (${\displaystyle z}$） さもないと。

に基づくと${\displaystyle \operatorname {If} }$関数では、論理ジャンクタを簡単に定義できます。たとえば、定義すると${\displaystyle \operatorname {And} =\operatorname {If} \circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$すると、${\displaystyle \operatorname {And} (x,y)=\operatorname {If} (x,y,0)}$つまり、${\displaystyle \operatorname {And} (x,y)}$は、両方が真である場合に限り真である。${\displaystyle x}$そして${\displaystyle y}$真である（論理積${\displaystyle x}$そして${\displaystyle y}$)

同様に、${\displaystyle \operatorname {Or} =\operatorname {If} \circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$そして${\displaystyle \operatorname {Not} =\operatorname {If} \circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$論理和と否定の適切な定義につながる：${\displaystyle \operatorname {Or} (x,y)=\operatorname {If} (x,1,y)}$そして${\displaystyle \operatorname {Not} (x)=\operatorname {If} (x,0,1)}$。

上記の関数を使用する${\displaystyle \operatorname {Leq} }$、${\displaystyle \operatorname {Geq} }$そして${\displaystyle \operatorname {And} }$定義${\displaystyle \operatorname {Eq} =\operatorname {And} \circ (\operatorname {Leq} ,\operatorname {Geq} )}$等価述語を実装します。実際には、${\displaystyle \operatorname {Eq} (x,y)=\operatorname {And} (\operatorname {Leq} (x,y),\operatorname {Geq} (x,y))}$は、以下の場合に限り真である。${\displaystyle x}$等しい${\displaystyle y}$。

同様に定義${\displaystyle \operatorname {Lt} =\operatorname {Not} \circ \operatorname {Geq} }$述語「より小さい」を実装し、${\displaystyle \operatorname {Gt} =\operatorname {Not} \circ \operatorname {Leq} }$「より大きい」を実装します。

べき乗と素数判定は原始再帰関数である。原始再帰関数が与えられた場合${\displaystyle e}$、${\displaystyle f}$、${\displaystyle g}$、 そして${\displaystyle h}$、値を返す関数${\displaystyle g}$いつ${\displaystyle e\leq f}$そしてその価値は${\displaystyle h}$そうでなければ、原始的な再帰となる。

ゲーデル数を用いることで、原始再帰関数を拡張し、整数や有理数などの他の対象にも適用できるようになります。整数を標準的な方法でゲーデル数で符号化すれば、加算、減算、乗算などの算術演算はすべて原始再帰的になります。同様に、有理数をゲーデル数で表現すれば、体演算はすべて原始再帰的になります。

以下の例と定義は、Kleene 1974 、pp. 222–231からのものです。多くは証明付きで掲載されています。また、ほとんどはBoolos、Burgess & Jeffrey 2002 、pp. 63–70にも同様の名称で掲載されており、証明または例として挙げられています。正確な導出に応じて、対数 lo(x, y) または lg(x, y) が追加されています。  

以下では、記号「'」、例えば a' は、「～の後継者」を意味する原始記号であり、通常は「+1」、例えば a +1 = _{def a' と解釈されます。関数 16〜20 および #G は、原始再帰述語を}ゲーデル数として表現された「算術的」形式に変換したり、そこから抽出したりすることに関して特に興味深いものです。

1. 加算：a+b
2. 乗算: a×b
3. 指数計算: a ^b
4. 階乗 a!  : 0! = 1、a'! = a!×a'
5. pred(a): (前任者または減少): a > 0 の場合、a−1、それ以外の場合は 0
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 の場合 1、それ以外の場合 0
11. sg(a): signum(a): a=0 の場合 0、それ以外の場合 1
12. a | b: (a が b を割り切る): ある k に対して b = k × a ならば 0、そうでなければ 1
13. 剰余(a, b): bがaを割り切れない場合の余り。MOD(a, b)とも呼ばれる。
14. a = b: sg | a − b | (クリーネの慣例では、真を0、偽を1で表していましたが、現在では、特にコンピュータにおいては、その逆、つまり真を1、偽を0で表すのが最も一般的な慣例となっています。これは、ここでおよび次の項目でsgを~sgに変更することに相当します。)
15. a < b: sg( a' ∸ b )
16. Pr(a): a は素数である Pr(a) = _def a>1 & NOT(Exists c) _1<c<a [ c|a ]
17. p _i : i+1番目の素数
18. (a) _{i : p i}の指数a: p _i ^x |a かつ NOT(p _i ^x' |a)となる一意の x
19. lh(a): 非零指数の「長さ」または数
20. ^{lo(a, b): (a の底を b とする対数): a, b > 1 の場合、b x} | aとなる最大の x 、それ以外の場合は 0

以下では、略語x = _def x ₁ , ... x _n ; 意味上必要な場合は添え字が使用されることがあります。

• _{#A: 関数 Ψ と定数 q 1}、 ... q _nから明示的に定義できる関数 φ は、Ψ において原始再帰的である。
• #B: 有限和 Σ _y<z ψ( x , y) と積 Π _y<z ψ( x , y) は ψ において原始再帰的です。
• #C:述語 Q の各変数に関数 χ ₁ ,..., χ _mを代入して得られる述語P は、χ ₁ ,..., χ _m , Qに関して原始再帰的である。
• #D: 以下の述語は、Q および R において原始再帰的です。

• NOT_Q( x ) 。
• QまたはR：Q( x )VR( x )、
• QとR: Q( x ) & R( x )、
• Q は R を意味する: Q( x ) → R( x )
• QはRと同等である：Q( x )≡R( x )

• #E: 次の述語は、述語Rにおいて原始再帰的です。

• (Ey) _y<z R( x , y) ここで (Ey) _y<zは「z より小さい y が少なくとも 1 つ存在して、次のようになる」という意味です。
• (y) _y<z R( x , y) ここで (y) _y<zは「z より小さいすべての y に対して、次のことが成り立つ」という意味です。
• μy _y<z R( x , y)。演算子 μy _y<z R( x , y) は、いわゆる最小化演算子またはミュー演算子の有界形式です。定義は「R( x , y) が真となるような、z より小さい y の最小値。そのような値が存在しない場合は z 」です。

• #F: 場合分けによる定義: Q ₁、 ...、 Q _mが相互に排他的な述語(または "ψ( x ) は適用される最初の節によって与えられた値を持つ) であるように定義された関数は、φ ₁、 ...、 Q ₁、 ... Q _mに関して原始再帰的である。

φ( x ) =

• φ ₁ ( x ) Q ₁ ( x ) が真の場合、
• . . . . . . . . . . . . . . . . . . .
• Q _m ( x ) が真の場合、 φ _m ( x ) とします。
• φ _m+1 ( x ) それ以外の場合

• #G: φが次の式を満たす場合：

φ(y, x ) = χ(y, COURSE-φ(y; x ₂ , ... x _n ), x ₂ , ... x _{n )}の場合、φ は χ において原始再帰的である。コースオブバリュー関数の値 COURSE-φ(y; x _{2 to n} ) は、元の関数の値のシーケンス φ(0, x _{2 to n} ), ..., φ(y-1, x _{2 to n ) をエンコードする。}

の代わりに${\displaystyle C_{n}^{k}}$代替定義では、0 値ゼロ関数を 1 つだけ使用します。${\displaystyle C_{0}^{0}}$常にゼロを返す基本関数として、ゼロ関数、後継関数、および合成演算子から定数関数を構築します。

ロビンソン^{[ 10 ]は}、再帰規則のさまざまな制約を検討した。その1つは、関数hがパラメータx _iにアクセスできないいわゆる反復規則である（この場合、一般性を失うことなく、関数gは恒等関数であると仮定できる。なぜなら、一般の場合は代入によって得られるからである）。

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(y,f(y,x)).\end{aligned}}}$

彼は、すべての原始的な再帰関数のクラスが、この方法で依然として得られることを証明した。

Robinson ^{[ 10 ]}が考慮したもう 1 つの制約は、純粋な再帰であり、h は誘導変数yにアクセスできません。

${\displaystyle {\begin{aligned}f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k}),\\f(S(y),x_{1},\ldots ,x_{k})&=h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}$

グラッドストーン^{[ 11 ]}は、この規則で全ての原始的な再帰関数を生成できることを証明した。グラッドストーン^{[ 12 ]}はこれを改良し、以下の2つの制約の組み合わせ、すなわち純粋な反復規則だけでも十分であることを証明した。

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(f(y,x)).\end{aligned}}}$

さらなる改善が可能: セヴェリン^{[ 13 ]}は、パラメータのない純粋な反復規則、すなわち

${\displaystyle {\begin{aligned}f(0)&=0,\\f(S(y))&=h(f(y)),\end{aligned}}}$

初期関数のセットを切り捨て減算x ∸ yで拡張すれば、すべての単項原始再帰関数を生成するのに十分です。さらに初期関数として + を含めると、すべての原始再帰関数が得られます。

再帰のいくつかの形式は、実際には原始的な再帰関数を定義することもあります。これらの形式で定義すると、見つけやすくなったり、読み書きがより自然になったりする場合があります。値系列再帰は、原始的な再帰関数を定義します。相互再帰のいくつかの形式も、原始的な再帰関数を定義します。

LOOPプログラミング言語でプログラムできる関数は、まさに基本的な再帰関数です。これは、これらの関数の能力を異なる視点から捉えることを意味します。チューリング完全な言語と比較した場合、LOOP言語の主な制約は、各ループの実行回数がループ開始前に指定される点にあります。

原始的な再帰プログラミング言語の例としては、基本的な算術演算子（+と−、またはADDとSUBTRACTなど）、条件分岐と比較演算子（IF-THEN、EQUALS、LESS-THAN）、および境界付きループ（基本的なforループなど）を含む言語が挙げられます。forループでは、すべてのループに既知または計算可能な上限値（FOR i FROM 1 TO n、ループ本体でiもnも変更できない）が存在します。whileループやIF-THENとGOTOを組み合わせたような、より汎用的な制御構造は、原始的な再帰言語では認められません。

アルバート・R・マイヤーとデニス・M・リッチーが1967年の論文で発表したLOOP言語[ ^{14 ]は}、そのような言語の一つです。その計算能力は、基本的な再帰関数と一致します。LOOP言語の変種として、ダグラス・ホフスタッターの『ゲーデル、エッシャー、バッハ』に収録されているBlooPがあります。無限ループ（WHILE、GOTO）を追加することで、この言語は一般的な再帰言語となり、チューリング完全になります。これは、現実世界のすべてのコンピュータプログラミング言語と同様です。

原始再帰関数の定義によれば、その計算は（有限ステップ後に）あらゆる入力に対して停止する。一方、一般的な再帰関数においては、停止問題は決定不能である。