This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000026469 Reproduction Date:
In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that 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.
The μ-recursive functions (or partial μ-recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator.
The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the Ackermann function can be proven to be total recursive, but not primitive.
Initial or "basic" functions: (In the following the subscripting is per Kleene (1952) p. 219. For more about some of the various symbolisms found in the literature see Symbolism below.)
Operators:
The strong equality operator \simeq can be used to compare partial μ-recursive functions. This is defined for all partial functions f and g so that
holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.
In the equivalence of models of computability, a parallel is drawn between Turing machines that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).
A normal form theorem due to Kleene says that for each k there are primitive recursive functions U(y)\! and T(y,e,x_1,\ldots,x_k)\! such that for any μ-recursive function f(x_1,\ldots,x_k)\! with k free variables there is an e such that
The number e is called an index or Gödel number for the function f. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.
Minsky (1967) observes (as does Boolos-Burgess-Jeffrey (2002) pp. 94–95) that the U defined above is in essence the μ-recursive equivalent of the universal Turing machine:
A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following we will abbreviate the string of parameters x_{1}, ..., x_{n} as x:
Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starting with 3 initial functions
He arrives at:
Cryptography, Artificial intelligence, Software engineering, Science, Machine learning
Set theory, Logic, Model theory, Mathematics, Foundations of mathematics
Alan Turing, Computer science, Logic, Turing machine examples, Mathematics
India, Set theory, Mesoamerica, Logic, MathWorld
Computability theory, Computable function, Primitive recursive function, Hyperoperation, Knuth's up-arrow notation
Turing machine, Computational complexity theory, Pi, Hypercomputation, Mathematical logic
Mathematics, Constructivism (mathematics), Computable analysis, Alan Turing, Real numbers
Number theory, Set theory, Proof theory, Turing machine, Mathematical logic
Hypercomputation, Alan Turing, Turing machine, Recursion, Lambda calculus
Syntax, GOTO (programming language), WHILE (programming language), Primitive recursive function, Uwe Schöning