値の経路の再帰

計算可能性理論において、値の経過の再帰は、再帰によって数論的関数を定義する手法です。値の経過の再帰による関数fの定義では、 f ( n ) の値はシーケンスから計算されます。 ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$

このような定義は、より単純な形式の再帰を使用した定義に変換できるという事実は、値の経過再帰によって定義された関数が原始再帰的であることを証明するためによく使用されます。値の経過再帰とは対照的に、原始再帰では関数の値の計算には前の値のみが必要です。たとえば、1 項原始再帰関数gの場合、 g ( n +1)の値はg ( n ) とnのみから計算されます。

階乗関数n !は、次の規則によって再帰的に定義される。

${\displaystyle 0!=1,}$

${\displaystyle (n+1)!=n!(n+1).}$

この再帰は、関数の次の値 ( n +1)! をnの値と関数の前の値n ! に基づいて計算するため、原始的な再帰です。一方、n番目のフィボナッチ数を返す関数 Fib( n )は、再帰方程式で定義されます。

${\displaystyle Fib(0)=0,}$

${\displaystyle フィボナッチ(1)=1,}$

${\displaystyle Fib(n+2)=Fib(n+1)+Fib(n).}$

Fib( n +2)を計算するには、Fib関数の最後の2つの値が必要です。最後に、再帰方程式で定義された 関数gを考えます。

${\displaystyle g(0)=0,}$

${\displaystyle g(n+1)=\sum _{i=0}^{n}g(i)^{ni}.}$

これらの式を使用してg ( n +1)を計算するには、 gの以前の値をすべて計算する必要があります。一般に、 gの計算には、固定された有限数の以前の値だけでは不十分です。関数 Fib とg は、値の経過の再帰によって定義される関数の例です。

一般に、 関数fは、すべてのnに対して、

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$

ここで、は指定されたシーケンスをエンコードするゲーデル数です。特に ${\displaystyle \langle f(0),f(1),\ldots ,f(n-1)\rangle }$

${\displaystyle f(0)=h(0,\langle \rangle )}$

再帰の初期値を提供します。関数hは最初の引数をテストして明示的な初期値を提供します。たとえばFibの場合は、次のように定義される関数を使用できます。

${\displaystyle h(n,s)={\begin{cases}n&{\text{if }}n<2\\s[n-2]+s[n-1]&{\text{if }}n\geq 2\end{cases}}}$

ここで、s [ i ] はエンコードされたシーケンスsから要素iを抽出することを表します。これは、原始的な再帰関数であることが簡単にわかります (適切なゲーデル番号が使用されていると仮定)。

値過程再帰による定義を原始再帰に変換するには、補助（ヘルパー）関数を使用します。

${\displaystyle f(n)=h(n,\langle f(0),f(1),\ldots ,f(n-1)\rangle )}$。

原始再帰を使ってfを定義するには、まず次の式を満たす 補助的な値関数を定義する。

${\displaystyle {\bar {f}}(n)=\langle f(0),f(1),\ldots ,f(n-1)\rangle }$

ここで、右辺は数列のゲーデル数列とみなされます。

したがって、fの最初のn個の値がエンコードされます。関数は、新しい要素に追加することで得られるため、原始的な再帰によって定義できます。 ${\displaystyle {\bar {f}}(n)}$${\displaystyle {\bar {f}}}$${\displaystyle {\bar {f}}(n+1)}$${\displaystyle {\bar {f}}(n)}$${\displaystyle h(n,{\bar {f}}(n))}$

${\displaystyle {\bar {f}}(0)=\langle \rangle }$、

${\displaystyle {\bar {f}}(n+1)={\mathit {append}}(n,{\bar {f}}(n),h(n,{\bar {f}}(n))),}$

ここで、append ( n , s , x )は、s が長さnのシーケンスをエンコードするたびに、 i < nのすべてについてt [ n ] = xかつt [ i ] = s [ i ]となるような長さn + 1の新しいシーケンスtを計算します。これは、適切なゲーデル番号付けを前提とした原始再帰関数です。つまり、hはそもそも原始再帰であると想定されます。したがって、再帰関係は原始再帰として記述できます。

${\displaystyle {\bar {f}}(n+1)=g(n,{\bar {f}}(n))}$

ここでgはそれ自体が原始再帰的であり、次のような 2 つの関数の組み合わせです。

${\displaystyle g(i,j)={\mathit {append}}(i,j,h(i,j)),}$

が与えられると、元の関数f はによって定義することができ、これはそれが原始再帰関数でもあることを示しています。 ${\displaystyle {\bar {f}}}$${\displaystyle f(n)={\bar {f}}(n+1)[n]}$

原始再帰関数の文脈では、有限の自然数列を単一の自然数として表現する手段があると便利です。そのような方法の1つであるゲーデルの符号化は、正の整数列を次のように 表現します。${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$

${\displaystyle \prod _{i=0}^{k}p_{i}^{n_{i}}}$、

ここで、p _{i は}i番目の素数を表す。この表現では、シーケンスに対する通常の操作はすべて原始再帰的であることが示される。これらの操作には以下が含まれる。

• シーケンスの長さを決定する
• インデックスを指定してシーケンスから要素を抽出する。
• 2 つのシーケンスを連結します。

このシーケンスの表現を使用すると、h ( m )が原始再帰的である場合、関数

${\displaystyle f(n)=h(\langle f(0),f(1),f(2),\ldots ,f(n-1)\rangle )}$。

原始再帰でもあります。

シーケンスにゼロが含まれる場合は、代わりに次のように表されます。 ${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$

${\displaystyle \prod _{i=0}^{k}p_{i}^{(n_{i}+1)}}$、

これにより、シーケンスとのコードが区別可能になります。 ${\displaystyle \langle 0\rangle }$${\displaystyle \langle 0,0\rangle }$

すべての再帰的定義を原始再帰的定義に変換できるわけではありません。 1 つの既知の例は、A ( m、n )の形式を持ち、原始再帰的ではないことが証明されているアッカーマン関数です。

実際、すべての新しい値A ( m +1, n ) は、以前に定義された値のシーケンスA ( i、j ) に依存しますが、このシーケンスに含まれる値であるiとjは、関数の以前に計算された値、つまり ( i、j ) = ( m、A ( m +1, n )) に依存します。したがって、上で提案した方法では、以前に計算された値のシーケンスを原始再帰的にエンコードすることはできません (この関数は原始再帰的ではないため、エンコードすることはできません)。

• Hinman, PG, 2006, 「数学論理の基礎」、AK Peters。
• Odifreddi, PG、1989 年、「Classical Recursion Theory」、North Holland、第 2 版、1999 年。