In
recursive function theory
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
, double recursion is an extension of
primitive recursion
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...
which allows the definition of non-primitive recursive functions like the
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
.
Raphael M. Robinson called functions of two
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
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
Rózsa Péter, until January 1934 Rózsa Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician. She is best known as the "founding mother of recursion theory".
Early life and education
Péter was bor ...
)
* ''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 computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
.
See also
*
Primitive recursion
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...
*
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
References
{{mathlogic-stub
Computability theory
Recursion