一般的な再帰関数

One of several equivalent definitions of a computable function

数理論理学とコンピュータサイエンスにおいて、一般再帰関数、部分再帰関数、あるいはμ-再帰関数は、自然数から自然数への部分関数であり、直感的にも形式的にも「計算可能」である。関数が全再帰関数である場合、全再帰関数（再帰関数と略されることもある）とも呼ばれる。 ^[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. 合成演算子 （置換演算子とも呼ばれる）：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{where the k+1 -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)次関数が与えられた場合、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にのみ適用することを要求している^{[7] [ 8]}。これはここで与えられた定義と比較してμ演算子を限定するものの、μ再帰関数のクラスはクリーネの正規形定理（下記参照）から導かれる通り、同じままである。^{[5] [6]}唯一の違いは、計算可能関数（すなわちμ再帰関数）が全関数であるかどうかが決定不能であるのと同様に、特定の関数定義がμ再帰関数を定義するかどうかが決定不能となることである。^[7]

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

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

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

例

最小化演算子を含まない例は、プリミティブ再帰関数#例にあります。

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

• xの整数平方根は、を満たす最小のzとして定義できる。最小化演算子を用いると、一般的な再帰定義は となり、ここでNot、Gt、Mulはそれぞれ論理否定、大なり、乗算である^[9]。実際、は ${\displaystyle (z+1)^{2}>x}$ ${\displaystyle \operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))}$ ${\displaystyle (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)}$0が成り立つ場合、かつその場合に限ります。したがって、が成り立つような最小のzは です。Gtは真理値を次のように符号化するため、否定接続詞Not が必要です。 ${\displaystyle S(z)*S(z)>x}$ ${\displaystyle \operatorname {Isqrt} (x)}$ ${\displaystyle S(z)*S(z)>x}$ 1、μは0。

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

• ^{[例が必要]}

全再帰関数

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

他の計算可能性モデルとの同等性

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

正規形定理

クリーネによる正規形定理によれば、各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]の構築に費やしたのと同じである。

象徴主義

文献では様々な記号が用いられています。これらの記号を用いる利点は、演算子を互いに「入れ子」にすることで関数の導出を簡潔に記述できることです。以下では、パラメータ列は次のように略記されます。 ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x}$

• 定数関数: Kleene では " " が使用され、Boolos-Burgess-Jeffrey (2002) (BBJ) では略語 " " が使用されます。 ${\displaystyle C_{q}^{n}(x)=q}$ ${\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}$

• 後継機能：クリーネは「後継者」の代わりに「and 」を使用します。「後継者」は原始的な意味を持つため、ほとんどのテキストでは次のようにアポストロフィを使用します。 ${\displaystyle x'}$ ${\displaystyle S}$

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

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

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

• 恒等関数:Kleene(1952)は変数の恒等関数を示すために使用します。BBJは変数の恒等関数を次の目的で使用します。 ${\displaystyle U_{i}^{n}}$ ${\displaystyle x_{i}}$ ${\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}$

• 合成（置換）演算子：Kleeneは太字を使用しています（ 「後継」演算子と混同しないように！）。上付き文字は関数、下付き文字は変数を表します。 ${\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}}$

• 原始再帰：Kleene では 記号が使用され、n は変数の数を示します。BBJ では が使用されます。以下が与えられます。 ${\displaystyle R^{n}({\text{base step}},{\text{induction step}})}$ ${\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}$

• 基本ステップ: U ${\displaystyle f(0,a)=a=U_{1}^{1}(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関数

参照

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

参考文献

1. 「再帰関数」スタンフォード哲学百科事典。スタンフォード大学形而上学研究室。2021年。
2. スタンフォード哲学百科事典、再帰関数の項、1.7節：「[μ-再帰関数のクラス]は、アラン・チューリングによって導入されたチューリング計算可能関数のクラス、およびアロンゾ・チャーチによって導入されたλ-定義可能関数のクラスと一致することが判明しました。」
3. Kleene, Stephen C. (1936). 「λ-定義可能性と再帰性」 . Duke Mathematical Journal . 2 (2): 340– 352. doi :10.1215/s0012-7094-36-00227-2.
4. チューリング、アラン・マティソン(1937年12月). 「計算可能性とλ-定義可能性」.記号論理ジャーナル. 2 (4): 153– 163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046.153ページの証明の概要: ^[3] ${\displaystyle \lambda {\mbox{-definable}}}$ ${\displaystyle {\stackrel {triv}{\implies }}}$ ${\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}$ ${\displaystyle {\stackrel {160}{\implies }}}$ ${\displaystyle {\mbox{Turing computable}}}$ ${\displaystyle {\stackrel {161}{\implies }}}$ ${\displaystyle \mu {\mbox{-recursive}}}$ ${\displaystyle {\stackrel {Kleene}{\implies }}}$ ${\displaystyle \lambda {\mbox{-definable}}}$
5. エンダートン、HB、「論理への数学的入門」、アカデミックプレス、1972年
6. Boolos, GS, Burgess, JP, Jeffrey, RC, Computability and Logic, Cambridge University Press, 2007
7. Jones, ND, 計算可能性と複雑性：プログラミングの観点から、MITプレス、マサチューセッツ州ケンブリッジ、ロンドン、イギリス、1997年
8. Kfoury, AJ, RN Moll, MA Arbib, 計算可能性へのプログラミング的アプローチ, 第2版, Springer-Verlag, ベルリン, ハイデルベルク, ニューヨーク, 1982
9. 原始再帰関数#ジャンクタ、原始再帰関数#等価述語、および原始再帰関数#乗算で定義されています
10. Stephen Cole Kleene (1943年1月). 「再帰述語と量指定子」(PDF) .アメリカ数学会誌. 53 (1): 41– 73. doi : 10.1090/S0002-9947-1943-0007371-8 .
11. ミンスキー1972、189ページ。

• クリーネ、スティーブン（1991）[1952] 『メタ数学入門』ウォルターズ＝ノードホフ＆ノースホランド社。ISBN 0-7204-2103-9。
• Soare, R. (1999) [1987]. 再帰的に可算な集合と次数：計算可能関数と計算可能生成集合の研究. Springer-Verlag. ISBN 9783540152996。
• ミンスキー、マーヴィン・L. (1972) [1967].計算：有限機械と無限機械. プレンティス・ホール. pp.  210–5 . ISBN 9780131654495。

210 ～ 215 ページで、ミンスキー氏はレジスタ マシンモデルを使用して μ 演算子を作成する方法を示し、それが一般的な再帰関数と同等であることを示しています。

• ブーロス、ジョージ、バージェス、リチャード・ジェフリー(2002). 「6.2 最小化」.計算可能性と論理（第4版）. ケンブリッジ大学出版局. pp.  70– 71. ISBN 9780521007580。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=General_recursive_function&oldid=1322119151"