General recursive function: Difference between revisions

Revision as of 03:32, 5 November 2003

Revision as of 20:01, 11 December 2003

Line 1:

The '''recursive functions''' are a class of [[function]]s from [[natural number]]s to [[natural number]]s which are "computable" in some intuitive sense. In fact, in [[computability theory]] it is shown that the recursive functions are precisely the functions that can be computed by [[Turing machine]]s. Recursive functions are related to [[primitive recursive function|primitive recursive functions]], and their inductive definition (below) builds upon that of the primitive recursive functions.

Not every recursive fuctionfunction is primitive recursive as well - the most famous example is the [[Ackermann function]].

Other equivalent function classes are the [[lambda-recursive function|λ-recursive functions]] and the functions that can be computed by [[Markov algorithm]]s.