Search: in
Double recursion
Double recursion in Encyclopedia Encyclopedia
  Tutorials     Encyclopedia     Videos     Books     Software     DVDs  
       





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(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.[1]

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(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.

See also

References






Source: Wikipedia | The above article is available under the GNU FDL. | Edit this article



Search for Double recursion in Tutorials
Search for Double recursion in Encyclopedia
Search for Double recursion in Videos
Search for Double recursion in Books
Search for Double recursion in Software
Search for Double recursion in DVDs
Search for Double recursion in Store




Advertisement




Double recursion in Encyclopedia
Double_recursion top Double_recursion

Home - Add TutorGig to Your Site - Disclaimer

©2011-2013 TutorGig.info All Rights Reserved. Privacy Statement