go-v.orgcodex
Menu
Page tools

codex · Philosophy

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.

Wikipedia contributors, "Double recursion", Wikipedia, revision 1196926053, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex