Double recursion
Introduction 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.
See also * Primitive recursion* Ackermann function
References