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.
Contents
Definition
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 set of total recursive functions is a subset of the partial recursive functions and is a superset of the primitive recursive functions; functions like the Ackermann function can be proven to be total recursive, and not primitive.
The first three functions are called the "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.)
The strong equality operator 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.
Full article ▸
