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 can be determined ...
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 computable function that is not primitive recursive. All primitive recursive functions are total ...
.
Raphael M. Robinson called functions of two
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
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, born 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 born in Budapest, ...
)
* ''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 computable function that is not primitive recursive. All primitive recursive functions are total ...
.
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 can be determined ...
*
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
References
{{mathlogic-stub
Computability theory
Recursion