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. 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.

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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1196926053 under CC BY-SA 4.0; modifications have been made.