一般的な再帰関数

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

他の同等の関数のクラスとしては、ラムダ計算の関数と、マルコフアルゴリズムによって計算できる関数があります。

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

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

合成と原始再帰の下で閉じている（つまり、最小化のない）初期関数とを含む関数の最小のクラスは、原始再帰関数のクラスです。すべての原始再帰関数は完全ですが、部分再帰関数はそうではありません。たとえば、後続関数の最小化は未定義です。原始再帰関数は完全再帰関数のサブセットであり、完全再帰関数は部分再帰関数のサブセットです。たとえば、アッカーマン関数は完全再帰であり、非原始的であることが証明できます。

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

1. 定数関数C^けーん
   _​: 任意の自然数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. 合成演算子 （置換演算子とも呼ばれる）：m項関数とm個のk項関数が与えられた場合： ${\displaystyle \circ \,}$${\displaystyle h(x_{1},\ldots ,x_{m})\,}$${\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項関数とk +2 項関数が与えられた場合: ${\displaystyle g(x_{1},\ldots ,x_{k})\,}$${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$

   ${\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{k+1 次関数 }}f{\text{ は次のように定義されます}}\\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)次関数が与えられた場合、k次関数は次のように定義されます。 ${\displaystyle f(y,x_{1},\ldots ,x_{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]他の}教科書ではμ演算子を全関数fにのみ適用することを要求しています。これはここで与えられた定義と比較してμ演算子を制限しますが、μ再帰関数のクラスは同じままであり、これはクリーネの正規形定理（下記参照）に従います。^{[5] [6]}唯一の違いは、計算可能な（つまりμ再帰的な）関数が全関数であるかどうかが決定できないのと同じように、特定の関数定義がμ再帰関数を定義するかどうかが決定できなくなることです。^[7]

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

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

任意の引数の選択に対して、両方の関数が定義されていてその値が等しいか、両方の関数が未定義である場合にのみ成立します。

最小化演算子を含まない例は、プリミティブ再帰関数#例で参照できます。

以下の例は、最小化演算子の使用方法を示すことのみを目的としています。これらはすべて原始再帰であるため、より複雑な方法ではありますが、最小化演算子なしで定義することもできます。

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

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

計算可能性モデルの同等性では、特定の入力に対して終了しないチューリング マシンと、対応する部分再帰関数におけるその入力に対する未定義の結果との間に類似点が描かれます。無限検索演算子は、プリミティブ再帰のルールでは定義できません。これは、これらのルールが「無限ループ」(未定義の値) のメカニズムを提供しないためです。

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

${\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]の構築に費やしたのと同じである。

文献では、さまざまな記号が使用されています。記号を使用する利点は、演算子を互いに「ネスト」して関数を導出すると、簡潔な形式で記述しやすくなることです。以下では、パラメータの文字列 x ₁、...、x _{n は}xと省略されています。

• 定数関数：Kleeneは「C^いいえ
  _​( x ) = q "とBoolos-Burgess-Jeffrey (2002) (BBJ)は略語 " const _n ( x ) = n "を使用します。

例:C⁷
₁₃（r、s、t、u、v、w、x）= 13

例えば、const ₁₃ ( r, s, t, u, v, w, x ) = 13

• 後継機能: Kleene は「後継」を表すために x' と S を使用します。「後継」はプリミティブであると考えられるため、ほとんどのテキストでは次のようにアポストロフィを使用します。

S(a) = a +1 = _def a'、ここで 1 = _def 0'、2 = _def 0 '' など。

• 恒等関数：Kleene（1952）は「U^に
  _私は「変数x _iに対する恒等関数を示す。BBJは恒等関数idを使用する。^に
  _私は変数 x ₁から x _nまで:

あなた^に
_私は( x ) = id^に
_私は( x ) = x _{i の}

例:U⁷
₃= id⁷
₃( r, s, t, u, v, w, x ) = t

• 合成（置換）演算子：Kleeneは太字のSを使用する^m
  _n(「後継者」の S と混同しないでください。 )上付き文字の「m」は関数「f _{m 」の m}^番目を指し、下付き文字の「n」は変数「x _{n 」の n}^番目の値を指します。

h( x )= g( f ₁ ( x )、...、f _m ( x ) ) が与えられている場合

h( x ) = S である。ⁿ
_m(g, f ₁ , ... , f _m )

同様の方法で、ただし上付き文字と下付き文字なしで、BBJ は次のように書いています。

h( x' )= Cn[g, f ₁ ,..., f _m ]( x )

• 原始再帰: Kleene はシンボル「R ⁿ (基本ステップ、誘導ステップ) 」を使用します。ここで n は変数の数を示します。BBJ は「 Pr(基本ステップ、誘導ステップ)( x ) 」を使用します。与えられた値:

• 基本ステップ: h( 0, x )= f( x )、および
• 帰納法のステップ: h( y+1, x ) = g( y, h(y, x ), x )

例: a + b のプリミティブ再帰定義:

• 基本ステップ: f( 0, a ) = a = U¹
  ₁(ア)
• 帰納法のステップ: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U³
  ₂( b, c, a ))

R ² { ウ¹
₁(a)、S [ (U³
₂( b, c, a ) ] }

P{ U¹
₁(a)、S[ (U³
₂( b, c, a ) ] }

例: Kleeneは、f(b, a) = b + a (変数aとbの逆に注意)の再帰的導出を実行する方法の例を示しています。彼は3つの初期関数から始めます。

1. S(a) = a'
2. あなた¹
   ₁(a) = a
3. あなた³
   ₂(b,c,a) = c です
4. g(b, c, a) = S(U³
   ₂( b, c, a )) = c'
5. 基本ステップ: h( 0, a ) = U¹
   ₁(ア)

誘導ステップ: h( b', a ) = g( b, h( b, a ), a )

彼は到着します:

a+b = R ² [ U¹
₁、S³
₁（S、U³
₂) ]

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

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

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