μ-recursive Function
In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers which are "computable" in an 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. The μ-recursive functions are closely 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.
Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms.
The set of all recursive functions is known as R in computational complexity theory.
Read more about μ-recursive Function: Definition, Equivalence With Other Models of Computability, Normal Form Theorem, Symbolism, Examples
Famous quotes containing the word function:
“The fact remains that the human being in early childhood learns to consider one or the other aspect of bodily function as evil, shameful, or unsafe. There is not a culture which does not use a combination of these devils to develop, by way of counterpoint, its own style of faith, pride, certainty, and initiative.”
—Erik H. Erikson (1904–1994)