再帰関数理論において、二重再帰は原始再帰の拡張であり、アッカーマン関数のような非原始再帰関数の定義を可能にします。
ラファエル・M・ロビンソンは、与えられた関数に関して、 2つの自然数変数の関数G（n、 x ）が二重再帰的であると呼んだ。
- G (0, x ) はxの与えられた関数です 。
- G ( n + 1, 0)は関数G ( n , ·)と与えられた関数 からの代入によって得られる。
- G ( n + 1, x + 1)は、 G ( n + 1, x )、関数G ( n ,·)、および与えられた関数 からの置換によって得られる。[1]
ロビンソンはさらに、特定の二重再帰関数（元々はロザ・ペーテルによって定義されたもの） を提供する。
- G (0, x ) = x + 1
- G ( n + 1, 0) = G ( n , 1)
- G ( n + 1, x + 1) = G ( n , G ( n + 1, x ))
ここで、与えられた関数は原始再帰的であるが、Gは原始再帰的ではない。実際、これはまさに現在アッカーマン関数として知られている関数である。
参照
参考文献
