Double recursion
Encyclopedia
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
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...

.

Raphael M. Robinson
Raphael M. Robinson
Raphael Mitchel Robinson was an American mathematician.Born in National City, California, Robinson was the youngest of four children of a lawyer and a teacher. He was awarded the BA , MA , and Ph.D. , all in mathematics, and all from the University of California, Berkeley. His Ph.D...

 called functions of two natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

 variables G(nx) 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
Rózsa Péter , Hungarian name Péter Rózsa, was a Hungarian mathematician. She is best known for her work with recursion theory....

)
  • G(0, x) = x + 1
  • G(n + 1, 0) = G(n, 1)
  • G(n + 1, x + 1) = G(nG(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
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...

.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK