Dvojitá rekurze - Double recursion - Wikipedia
v teorie rekurzivních funkcí, dvojitá rekurze je příponou primitivní rekurze což umožňuje definici neprimitivních rekurzivních funkcí, jako je Ackermannova funkce.
Raphael M. Robinson nazývané funkce dvou přirozené číslo proměnné G(n, X) dvojitý rekurzivní s ohledem na dané funkce, pokud
- G(0, X) je daná funkceX.
- G(n + 1, 0) se získá substitucí z funkce G(n, ·) A dané funkce.
- G(n + 1, X + 1) se získá substitucí z G(n + 1, X), funkce G(n, ·) A dané funkce.[1]
Robinson dále poskytuje specifickou dvojitou rekurzivní funkci (původně definovanou Rózsa Péter )
- G(0, X) = X + 1
- G(n + 1, 0) = G(n, 1)
- G(n + 1, X + 1) = G(n, G(n + 1, X))
Kde dané funkce jsou primitivní rekurzivní, ale G není primitivní rekurzivní. Ve skutečnosti je to právě funkce nyní známá jako Ackermannova funkce.
Viz také
Reference
- ^ Raphael M. Robinson (1948). „Rekurze a dvojitá rekurze“. Bulletin of the American Mathematical Society. 54: 987–93. doi:10.1090 / S0002-9904-1948-09121-2.
 | Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |