General recursive function: Difference between revisions

Revision as of 17:28, 6 November 2004

Revision as of 22:53, 14 November 2004

Line 1:

[[Category:Computability]]

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.

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

Line 21 ⟶ 19:

It is interesting to note that if the application of the unbounded search operator in the definition above is limited strictly to ''regular functions'' (functions which are guaranteed to be total when the unbounded search operator is applied to them), the resulting set (historically called the ''general recursive functions'') is the same as the set of recursive functions -- in other words, the requirement for partial functions can be partially obviated.

[[Category:Computability]]

[[es:Función recursiva]]