In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
and
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a general recursive function, partial recursive function, or μ-recursive function is a
partial function
In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
from
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s to natural numbers that is "computable" in an intuitive sense – as well as in a
formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, it is shown that the μ-recursive functions are precisely the functions that can be computed by
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s (this is one of the theorems that supports the
Church–Turing thesis
In Computability theory (computation), computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) ...
). The μ-recursive functions are closely related to
primitive recursive function
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed befor ...
s, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
.
Other equivalent classes of functions are the functions of
lambda calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
and the functions that can be computed by
Markov algorithm
In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a gen ...
s.
The subset of all ''total'' recursive functions with values in is known in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
as the
complexity class R.
Definition
The μ-recursive functions (or general 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
minimization 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
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
can be proven to be total recursive, and to be non-primitive.
Primitive or "basic" functions:
#''Constant functions '': For each natural number and every
#::
#:Alternative definitions use instead a ''zero function'' as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator.
# ''Successor function S:''
#::
# ''Projection function''
(also called the ''Identity function''): For all natural numbers
such that
:
#::
Operators (the
domain of a function
In mathematics, the domain of a function is the Set (mathematics), set of inputs accepted by the Function (mathematics), function. It is sometimes denoted by \operatorname(f) or \operatornamef, where is the function. In layman's terms, the doma ...
defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result):
# ''Composition operator''
(also called the ''substitution operator''): Given an m-ary function
and m k-ary functions
:
#::
#:This means that
is defined only if
and
are all defined.
# ''Primitive recursion operator'' : Given the ''k''-ary function
and ''k''+2 -ary function
:
#::
#:This means that
is defined only if
and
are defined for all
Examples
Examples not involving the minimization operator can be found at
Primitive recursive function#Examples.
The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive.
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
Total recursive function
A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a
total Turing machine. There is no way to computably tell if a given general recursive function is total - see ''
Halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
''.
Equivalence with other models of computability
In the
equivalence of models of computability, a parallel is drawn between
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s 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).
Normal form theorem
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
:
f(x_1,\ldots,x_k) \simeq U(\mu(T)(e,x_1,\ldots,x_k)).
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 observes the
U defined above is in essence the μ-recursive equivalent of the
universal Turing machine:
Symbolism
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 the string of parameters x
1, ..., x
n is abbreviated as x:
* ''Constant function'': Kleene uses " C(x) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " const
n( x) = n ":
:: e.g. C ( r, s, t, u, v, w, x ) = 13
:: e.g. const
13 ( r, s, t, u, v, w, x ) = 13
* ''Successor function'': Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:
:: S(a) = a +1 =
def a', where 1 =
def 0', 2 =
def 0 ' ', etc.
* ''Identity function'': Kleene (1952) uses " U " to indicate the identity function over the variables x
i; B-B-J use the identity function id over the variables x
1 to x
n:
: U( x ) = id( x ) = x
i
: e.g. U = id ( r, s, t, u, v, w, x ) = t
* ''Composition (Substitution) operator'': Kleene uses a bold-face S (not to be confused with his S for "successor" ! ). The superscript "m" refers to the m
th of function "f
m", whereas the subscript "n" refers to the n
th variable "x
n":
:If we are given h( x )= g( f
1(x), ... , f
m(x) )
:: h(x) = S(g, f
1, ... , f
m )
:In a similar manner, but without the sub- and superscripts, B-B-J write:
:: h(''x)= Cn
1 ,..., fm">, f1 ,..., fmx)
* ''Primitive Recursion'': Kleene uses the symbol " R
n(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(x)". Given:
:* base step: h( 0, x )= f( x ), and
:* induction step: h( y+1, x ) = g( y, h(y, x),x )
: Example: primitive recursion definition of a + b:
::* base step: f( 0, a ) = a = U(a)
::* induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U( b, c, a ))
::: R
2
::: Pr
''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 starts with 3 initial functions
:# S(a) = a'
:# U(a) = a
:# U( b, c, a ) = c
:# g(b, c, a) = S(U( b, c, a )) = c'
:# base step: h( 0, a ) = U(a)
:: induction step: h( b', a ) = g( b, h( b, a ), a )
He arrives at:
:: a+b = R
2 U, S(S, U)
Examples
*
Fibonacci number
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
*
McCarthy 91 function
See also
*
Recursion theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
*
Recursion
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
*
Recursion (computer science)
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursion, recursive problems by using function (computer sc ...
References
*
*
*
:On pages 210-215 Minsky shows how to create the μ-operator using the
register machine
In mathematical logic and theoretical computer science, a register machine is a generic class of abstract machines, analogous to a Turing machine and thus Turing complete. Unlike a Turing machine that uses a tape and head, a register machine u ...
model, thus demonstrating its equivalence to the general recursive functions.
*
External links
Stanford Encyclopedia of Philosophy entryA compiler for transforming a recursive function into an equivalent Turing machine
{{DEFAULTSORT:Mu-Recursive Function
Computability theory
Theory of computation
ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция