Content deleted Content added
m added link to R complexity class |
clarify |
||
Line 1:
In [[mathematical logic]] and [[computer science]], the '''recursive functions''' are a class of [[function (mathematics)|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. However, not every recursive function is a primitive recursive function — the most famous example of one which is not 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.
| |||