Podwójna rekurencja
W teorii funkcji rekurencyjnych podwójna rekurencja jest rozszerzeniem rekurencji pierwotnej , która pozwala na zdefiniowanie nieprymitywnych funkcji rekurencyjnych, takich jak funkcja Ackermanna .
Raphael M. Robinson nazwał funkcje dwóch zmiennych liczb naturalnych G ( n , x ) podwójnie rekurencyjnymi względem danych funkcji , jeśli
- G (0, x ) jest daną funkcją x .
- G ( n + 1, 0) otrzymuje się przez podstawienie z funkcji G ( n , ·) i danych funkcji.
- G ( n + 1, x + 1) otrzymuje się przez podstawienie z G ( n + 1, x ), funkcji G ( n , ·) i danych funkcji.
Robinson dalej zapewnia specyficzną podwójną funkcję rekurencyjną (pierwotnie zdefiniowaną przez Rózsę Péter )
- sol (0, x ) = x + 1
- sol ( n + 1, 0) = sol ( n , 1)
- sol ( n + 1, x + 1) = sol ( n , sol ( n + 1, x ))
gdzie dane funkcje są prymitywnie rekurencyjne, ale G nie jest prymitywnie rekurencyjne. W rzeczywistości jest to dokładnie funkcja znana obecnie jako funkcja Ackermanna .