基本的な再帰関数

「基本」 という用語は、もともと計算可能性理論の文脈でラースロー・カルマールによって導入されました。^{[ 1 ] [ 2 ]}彼は、基本再帰関数（「カルマール基本関数」 ）のクラスを、原始再帰関数のサブセットとして定義しました。具体的には、合成、有界和、有界積などの限られた演算セットを使用して計算できる関数です。^{[ 3 ]}これらの関数は、固定高さの指数関数の塔（例えば、${\displaystyle O(2^{2^{n}})}$すべての原始再帰関数が基本関数であるとは限りません。たとえば、テトレーションは成長が速すぎるため、基本クラスには含まれません。基本再帰関数はクラスに対応します。$\displaystyle {\mathcal {E}}^{3}}$グジェゴルチク階層の。^{[ 4 ]}

計算複雑性理論において、 「ELEMENTARY」という用語は、基本時間で解ける決定問題のクラス、つまり、ある固定数の指数関数で制限された時間内で解ける決定問題のクラスを指します。正式には次のようになります。

${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}$

どこ${\displaystyle \exp ^{k}(n)}$kレベルの指数タワーを表します(例:${\displaystyle 2^{2^{\cdot ^{\cdot ^{n}}}}}$)

名前は同じ歴史的起源に由来するものの、ELEMENTARY複雑性クラスは、関数全体ではなく、決定問題とチューリングマシンの実行時間を扱います。

基本再帰関数の定義は、原始再帰関数の定義と同じですが、原始再帰が有界総和と有界積に置き換えられています。^{[ 1 ] [ 3 ] [ 5 ]}すべての関数は自然数上で動作します。基本関数はすべて基本再帰関数であり、次のとおりです。

1. ゼロ関数。ゼロを返します。${\displaystyle f(x)=0}$。
2. 後継関数：${\displaystyle f(x)=x+1}$多くの場合、これは次のように表されます。${\displaystyle S}$例えば${\displaystyle S(x)}$後続関数を繰り返し適用することで、加算を実現できる。
3. 射影関数：これらは引数を無視するために使用されます。たとえば、${\displaystyle f(a,b)=a}$これは射影関数です。
4. 減算関数：${\displaystyle f(x,y)=\max(x-y,0)}$この関数は、条件分岐と反復処理を定義するために使用されます。

これらの基本関数から、他の基本的な再帰関数を構築することができる。

1. 合成：ある基本再帰関数の値を別の基本再帰関数の引数として適用すること。${\displaystyle f}$組成として定義される${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}}$基本的な再帰である場合${\displaystyle h}$は基本的な再帰であり、それぞれ${\displaystyle g_{i}}$基本的な再帰です。
2. 制限付き総和：${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$基本的な再帰である場合${\displaystyle g}$基本的な再帰です。
3. 境界積：${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$基本的な再帰である場合${\displaystyle g}$基本的な再帰です。

計算可能性理論の文脈において、重ね合わせとは、関数合成によって既存の関数から新しい関数を構築する方法である。これにより、1つまたは複数の関数の出力を別の関数の入力として利用することが可能になる。

より厳密に言えば、次のような場合を想定します。

• ${\displaystyle f(x_{1},\dots ,x_{k})}$は${\displaystyle k}$項関数、
• ${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})}$は${\displaystyle n}$引数関数。

そしてこれらの関数の重ね合わせによって新しい${\displaystyle n}$-項関数:

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}$。

基本再帰関数のクラスは、射影関数と以下の初期関数セットのいずれかの重ね合わせによる閉包と一致する。

• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$^{[ 6 ]}
• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;nm,\;n^{m}\}}$^{[ 7 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}$^{[ 8 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}$^{[ 9 ]}

どこ${\displaystyle n\mathbin {\dot {-}} m=\max(n-m,0)}$切り捨て減算（monus）を表します。

2025年、ミハイ・プルネスク、ロレンツォ・サウラス＝アルトゥサラ、ジョセフ・M・シュニアは、カルマール基本関数のクラスが加算から帰納的に生成できることを証明した（${\displaystyle n+m}$）、整数剰余（${\displaystyle n{\bmod {m}}}$）と2進法（${\displaystyle 2^{n}}$）Mazzanti ^{[ 7 ]と Marchenkov [ 8 ]}による以前の結果を改善した。彼らはさらに、これら 3 つの演算によって定義される置換基底が最小であることを証明した。^{[ 10 ]}未解決の問題は、${\displaystyle \{n+m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$これは代替的な根拠である。

例１

させて $${\displaystyle f(a,b)=a{\bmod {b}},\quad g_{1}(n)=2^{n+n},\quad g_{2}(n)=2^{n}+n\,.}$$ 次に関数 $${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}$$ 二乗関数を定義する${\displaystyle h(n)=n^{2}}$重ね合わせのみによって。^{[ 11 ]}これは、明示的な再帰を必要とせずに、重ね合わせによって加算、整数の余り、および2進数のべき乗のみを使用して、平方などの関数を表現できることを示しています。

例２

基本的な再帰関数のもう1つの例は、クロネッカーのデルタです。$${\displaystyle \delta _{ij}=2^{(2^{i}{\bmod {(}}2^{j}+1))+(2^{j}{\bmod {(}}2^{i}+1)){\bmod {(}}2^{i}+2^{j})}{\bmod {2}}\,,}$$ これは以下を満たす${\displaystyle \delta _{ij}=1}$もし${\displaystyle i=j}$そして${\displaystyle 0}$さもないと。

その他の例

${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}$[ ^{12 ]​}

${\displaystyle 2xy=(x+y)^{2}\mathbin {\dot {-}} (x^{2}+y^{2})}$[ ^{13 ]​}

${\displaystyle \lfloor x/y\rfloor =(2(x+1)(x\mathbin {\dot {-}} (x{\bmod {y}}))){\bmod {(}}2(x+1)y\mathbin {\dot {-}} 1)}$[ ^{14 ]​}

${\displaystyle xy=\lfloor 2xy/2\rfloor }$[ ^{15 ]​}

${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}$[ ^{16 ]​}

低次の基本再帰関数は、上記の定義に従いますが、有界積は許可されません。^{[ 3 ]}つまり、低次の基本再帰関数は、零関数、後継関数、射影関数、他の低次の基本再帰関数の合成、または別の低次の基本再帰関数の有界和でなければなりません。

低次の基本再帰関数は、スコレム基本関数とも呼ばれます。^{[ 17 ] [ 18 ]}

基本的な再帰関数は指数関数以上の成長の可能性を秘めているのに対し、より低い基本的な再帰関数は多項式的な成長を示す。

低初等関数のクラスは、初等関数の場合と同様に、単純関数の合成という観点から記述されます。^{[ 18 ] [ 19 ]}すなわち、多項式で制限された関数は、射影、${\displaystyle n+1}$、${\displaystyle nm}$、${\displaystyle n\mathbin {\dot {-}} m}$、${\displaystyle n\wedge m}$、${\displaystyle \lfloor n/m\rfloor }$1 つの指数関数 (${\displaystyle 2^{n}}$または${\displaystyle n^{m}}$）ただし、数式の構造には次の制限があります。数式は指数に関して 2 階までしか持つことができません（例：${\displaystyle xy(z+1)}$1階建てで、${\displaystyle (x+y)^{yz+x}+z^{x+1}}$2階建てで、${\displaystyle 2^{2^{x}}}$（3階建てです）。${\displaystyle n\wedge m}$nとmのビットごとのAND演算です。

• 小学校
• 初等関数演算
• 原始的な再帰関数
• グジェゴルチク階層
• ループ（プログラミング言語）
• 実験時間