Recursive function

In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers 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 machines. Recursive functions are related to 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 is the Ackermann function.

Related Topics:
Mathematical logic - Computer science - Function - Natural number - Computability theory - Turing machine - Primitive recursive functions - Ackermann function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Other equivalent function classes are the λ-recursive functions and the functions that can be computed by Markov algorithms.

Related Topics:
λ-recursive functions - Markov algorithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~