一般的な再帰関数

数理論理学およびコンピュータ科学において、一般再帰関数、部分再帰関数、またはμ再帰関数は、自然数から自然数への部分関数であり、直感的な意味でも形式的な意味でも「計算可能」である。関数が全関数である場合、全再帰関数（再帰関数と略されることもある）とも呼ばれる。^{[ 1 ]}計算可能性理論では、μ再帰関数はチューリングマシンで計算できる関数であることが示される^{[ 2 ] [ 4 ]} （これはチャーチ・チューリングのテーゼを支持する定理の1つである）。μ再帰関数は原始再帰関数と密接に関連しており、その帰納的定義（下記）は原始再帰関数の定義に基づいている。ただし、すべての全再帰関数が原始再帰関数であるわけではない。最も有名な例はアッカーマン関数である。

他の同等の関数クラスとしては、ラムダ計算の関数やマルコフアルゴリズムで計算できる関数などが挙げられる。

値が{0,1}にある全再帰関数のサブセットは、計算複雑性理論において複雑性クラス Rとして知られています。

μ再帰関数（または一般再帰関数）は、有限個の自然数の組を受け取り、単一の自然数を返す部分関数です。これらは、初期関数を含み、合成、原始再帰、および最小化演算子μに関して閉じている、部分関数の最小クラスです。

初期関数を含み、合成と原始再帰（つまり最小化なし）に関して閉じている関数の最小クラスは、原始再帰関数のクラスです。すべての原始再帰関数は全再帰ですが、部分再帰関数ではそうではありません。たとえば、後継関数の最小化は定義されていません。原始再帰関数は全再帰関数の部分集合であり、全再帰関数は部分再帰関数の部分集合です。たとえば、アッカーマン関数は全再帰であり、非原始であることが証明できます。

基本関数または「プリミティブ」関数：

1. 定数関数C ^k _n : 各自然数nおよびすべてのkに対して

   ${\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$

   代替定義では、常にゼロを返すプリミティブ関数としてゼロ関数を使用し、ゼロ関数、後継関数、および合成演算子から定数関数を構築します。

2. 後継関数S:

   ${\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,}$

3. 射影関数${\displaystyle P_{i}^{k}}$（恒等関数とも呼ばれる）：すべての自然数に対して${\displaystyle i,k}$そのため${\displaystyle 1\leq i\leq k}$:

   ${\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}$

演算子（演算子によって定義される関数の定義域は、計算中に実行されるすべての関数適用が明確な結果をもたらすような引数の値の集合です）：

1. 合成演算子${\displaystyle \circ \,}$（置換演算子とも呼ばれる）：m項関数が与えられた場合${\displaystyle h(x_{1},\ldots ,x_{m})\,}$およびm k項関数${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$:

   ${\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}$

   これはつまり${\displaystyle f(x_{1},\ldots ,x_{k})}$は、以下の場合にのみ定義されます。${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}$そして${\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$すべて定義されています。

2. 原始再帰演算子ρ：k項関数が与えられた場合${\displaystyle g(x_{1},\ldots ,x_{k})\,}$およびk +2 項関数${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$:

   ${\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the }}k+1{\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}$

   これはつまり${\displaystyle f(y,x_{1},\ldots ,x_{k})}$は、以下の場合にのみ定義されます。${\displaystyle g(x_{1},\ldots ,x_{k})}$そして${\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$すべての${\displaystyle z<y.}$

3. 最小化演算子μ：( k +1)項関数が与えられた場合${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$k項関数${\displaystyle \mu (f)}$定義は以下のとおりです。

   ${\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}$

直感的に言えば、最小化は、0 から始めて上方向に進み、関数がゼロを返す最小の引数を探します。そのような引数がない場合、またはfが定義されていない引数に遭遇した場合、探索は決して終了しません。${\displaystyle \mu (f)}$引数に対して定義されていません${\displaystyle (x_{1},\ldots ,x_{k}).}$

一部の教科書ではここで定義したμ演算子を使用していますが、^{[ 5 ] [ 6 ]}他の教科書^{[ 7 ] [ 8 ]}ではμ演算子を全関数fにのみ適用することを要求しています。これはここで与えられた定義と比較してμ演算子を制限しますが、μ再帰関数のクラスは同じままであり、これはクリーネの標準形定理（下記参照）から導かれます。^{[ 5 ] [ 6 ]}唯一の違いは、特定の関数定義がμ再帰関数を定義するかどうかが決定不能になることです。これは、計算可能な（つまりμ再帰的な）関数が全関数であるかどうかが決定不能であるためです。^{[ 7 ]}

強い平等関係${\displaystyle \simeq }$部分μ再帰関数を比較するために使用できます。これは、すべての部分関数fとgに対して定義され、

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}$

この式が成り立つのは、引数の任意の選択に対して、両方の関数が定義されていてその値が等しいか、または両方の関数が未定義である場合に限る。

最小化演算子を使用しない例は、Primitive recursive function#Examplesで見つけることができます。

以下の例は、最小化演算子の使用方法を示すためのものであり、すべて原始的な再帰であるため、より複雑な方法ではあるものの、最小化演算子を使用せずに定義することも可能です。

以下の例は、原始的な再帰関数ではない一般的な再帰関数を定義しています。そのため、最小化演算子の使用を避けることはできません。

一般再帰関数は、すべての入力に対して定義される場合、または同等に、全チューリングマシンで計算できる場合、全再帰関数と呼ばれます。与えられた一般再帰関数が全再帰関数であるかどうかを計算によって判定する方法はありません（停止問題を参照）。

計算可能性モデルの等価性において、特定の入力に対して終了しないチューリングマシンと、対応する部分再帰関数におけるその入力に対する未定義の結果との間に類似性が見出される。無限探索演算子は、原始再帰の規則では定義できない。なぜなら、原始再帰の規則は「無限ループ」（未定義値）のメカニズムを提供しないからである。

クリーネによる正規形定理によれば、各 k に対して原始再帰関数が存在する。${\displaystyle U(y)\!}$そして${\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}$任意のμ-再帰関数に対して${\displaystyle f(x_{1},\ldots ,x_{k})\!}$k 個の自由変数を持つ、あるeが存在し、

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))}$。

数eは関数fのインデックスまたはゲーデル数と呼ばれます。^{[ 10 ] : 52–53} この結果の帰結として、任意の μ 再帰関数は、(全)原始再帰関数に適用される μ 演算子の単一のインスタンスを使用して定義できます。

ミンスキーは${\displaystyle U}$上記で定義したものは、本質的にはユニバーサルチューリングマシンのμ再帰版である。

Uを構築するとは、数nを正しく解釈し、 xの適切な関数を計算する一般再帰関数U ( n , x ) の定義を書き下すことである。Uを直接構築するには、ユニバーサルチューリングマシン^{[ 11 ]}の構築に費やしたのとほぼ同じ労力とほぼ同じ考え方が必要となる。

文献ではさまざまな記号が使用されています。記号を使用する利点は、演算子を互いに「入れ子」にすることで関数を導出する場合、簡潔な形式で記述しやすくなることです。以下では、パラメータの文字列を示します。${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$略称は${\displaystyle x}$:

• 定数関数: クリーネは「${\displaystyle C_{q}^{n}(x)=q}$" および Boolos-Burgess-Jeffrey (2002) (BBJ) は、" という略語を使用しています。${\displaystyle \mathrm {const} ^{n}(x)=n}$":

例えば${\displaystyle C_{13}^{7}(r,s,t,u,v,w,x)=13}$

例えば${\displaystyle \mathrm {const} ^{13}(r,s,t,u,v,w,x)=13}$

• 後継関数: クリーネは${\displaystyle x'}$そして${\displaystyle S}$「successor」の場合。「successor」は原始的な表現と考えられているため、ほとんどのテキストではアポストロフィを次のように使用します。

${\displaystyle S(a)=a+1;{\overset {\mathrm {def} }{=}};a'}$、 どこ

${\displaystyle 1{\overset {\mathrm {def} }{=}}0'}$、

${\displaystyle 2{\overset {\mathrm {def} }{=}}0''}$など

• 恒等関数：クリーネ（1952）は${\displaystyle U_{i}^{n}}$変数に関する恒等関数を示す${\displaystyle x_{i}}$; BBJは恒等関数を使用する${\displaystyle \mathrm {id} _{i}^{n}}$変数に関して${\displaystyle x_{1}}$に${\displaystyle x_{n}}$:

${\displaystyle U_{i}^{n}(x)=\mathrm {id} _{i}^{n}(x)=x_{i}}$

例えば${\displaystyle U_{3}^{7}(r,s,t,u,v,w,x)=\mathrm {id} _{3}^{7}(r,s,t,u,v,w,x)=t}$

• 合成（置換）演算子：クリーネは太字を使用する${\displaystyle \mathbf {S} _{m}^{n}}$（彼の${\displaystyle S}$（「後継者」のことです！）。上付き文字${\displaystyle m}$は${\displaystyle m^{th}}$関数${\displaystyle f_{m}}$添え字は${\displaystyle n}$は${\displaystyle n^{th}}$変数${\displaystyle x_{n}}$:

もし私たちに与えられたら

${\displaystyle h(x)=g(f_{1}(x),\ldots ,f_{m}(x))}$

それから

${\displaystyle h(x)=\mathbf {S} _{m}^{n}(g,f_{1},\ldots ,f_{m})}$

同様に、下付き文字と上付き文字なしで、BBJは次のように表記します。

${\displaystyle h(x')=Cg,f_{1},\ldots ,f_{m}}$

• 原始再帰: クリーネは記号を使用する${\displaystyle R^{n}({\text{base step}},{\text{induction step}})}$ここでnは変数の数を示します。BBJは${\displaystyle \Pr({\text{base step}},{\text{induction step}})(x)}$与えられた条件：

• 基本ステップ:${\displaystyle h(0,x)=f(x)}$
• 誘導段階：${\displaystyle h(y+1,x)=g(y,h(y,x),x)}$

例: 原始再帰の定義${\displaystyle a+b}$

• 基本ステップ:${\displaystyle f(0,a)=a=U_{1}^{1}(a)}$U ¹ ₁ (a)
• 誘導段階：${\displaystyle f(b',a)=(f(b,a))'=g(b,f(b,a),a)=g(b,c,a)=c'=S(U_{2}^{3}(b,c,a))}$

${\displaystyle R^{2}\left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

${\displaystyle \Pr \left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

例：クリーネは、再帰的導出を実行する方法の例を示しています。${\displaystyle f(b,a)=b+a}$（変数の反転に注意）${\displaystyle a}$そして${\displaystyle b}$彼は次のように始める。${\displaystyle 3}$初期関数

1. ${\displaystyle S(a)=a'}$
2. ${\displaystyle U_{1}^{1}(a)=a}$
3. ${\displaystyle U_{2}^{3}(b,c,a)=c}$
4. ${\displaystyle g(b,c,a)=S(U_{2}^{3}(b,c,a))=c'}$
5. 基本ステップ:${\displaystyle h(0,a)=U_{1}^{1}(a)}$

誘導段階：${\displaystyle h(b',a)=g(b,h(b,a),a)}$

彼は以下の場所に到着します。

${\displaystyle a+b=R^{2}\left(U_{1}^{1},;S_{1}^{3}(S,U_{2}^{3})\right)}$

• フィボナッチ数
• マッカーシー91機能

• 再帰理論
• 再帰
• 再帰（コンピュータサイエンス）

• スタンフォード哲学百科事典の項目
• 再帰関数を同等のチューリングマシンに変換するコンパイラ