Μ-recursive function

related topics
{math, number, function}
{theory, work, human}
{mi², represent, 1st}

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 \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.

Full article ▸

related documents
Original proof of Gödel's completeness theorem
Riemann integral
Pythagorean triple
Grothendieck topology
Binomial coefficient
Discrete cosine transform
Travelling salesman problem
Lie group
Group theory
Combinatorics
Class (computer science)
Determinant
P-adic number
Lambda calculus
Dedekind domain
Orthogonal matrix
Hilbert's tenth problem
Lebesgue integration
Algebraic geometry
Formal power series
Logarithm
Banach–Tarski paradox
Fast Fourier transform
Closure (computer science)
Continued fraction
Red-black tree
Singleton pattern
Axiom of choice
Tensor product
Adjoint functors