General recursive function: Difference between revisions

Revision as of 09:21, 25 September 2004

Revision as of 17:28, 6 November 2004

Line 1:

[[Category:Recursion theoryComputability]]

[[Category:computer science]]

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.