Double recursion

In recursive function theory, double recursion is an extension of primitive recursion which allows the definition of non-primitive recursive functions like the Ackermann function. Raphael M. Robinson called functions of two natural number variables G(n, x) double recursive with respect to given functions, if

* G(0, x) is a given function of x.
* G(n + 1, 0) is obtained by substitution from the function G(n, ·) and given functions.
* G(n + 1, x + 1) is obtained by substitution from G(n + 1, x), the function G(n, ·) and given functions.[1]

Robinson goes on to provide a specific double recursive function (originally defined by 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))

where the given functions are primitive recursive, but G is not primitive recursive. In fact, this is precisely the function now known as the Ackermann function.

## See also

* Primitive recursion
* Ackermann function

## References

1. ↑ Raphael M. Robinson (1948). "Recursion and Double Recursion". Bulletin of the American Mathematical Society 54 (10): 987–93. doi:10.1090/S0002-9904-1948-09121-2. http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bams/1183512393&page=record.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Double recursion. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Double_recursion&oldid=230776"