View source for General recursive function

{{Short description|One of several equivalent definitions of a computable function}}
In [[Mathematical logic|mathematical logic]] and [[Computer science|computer science]], a '''general recursive function''', '''partial recursive function''', or '''μ-recursive function''' is a [[Partial function|partial function]] from [[Natural number|natural number]]s to natural numbers that is "computable" in an intuitive sense – as well as in a [[Computable function|formal one]]. If the function is total, it is also called a '''total recursive function''' (sometimes shortened to '''recursive function''').<ref>{{Cite book|chapter-url=https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC|title = The Stanford Encyclopedia of Philosophy|chapter = Recursive Functions|year = 2021|publisher = Metaphysics Research Lab, Stanford University}}</ref> In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by [[Turing machine]]s<ref>[[Stanford Encyclopedia of Philosophy]], Entry [http://plato.stanford.edu/entries/recursive-functions Recursive Functions], Sect.1.7: "[The class of μ-recursive functions] ''turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church.''"</ref>{{#tag:ref|{{cite journal | jstor=2268280 |first=Alan Mathison |last=Turing |  title=Computability and λ-Definability | journal=[[Journal of Symbolic Logic]] | volume=2 | number=4 | pages=153–163 | date=Dec 1937 |doi=10.2307/2268280 |s2cid=2317046 }} Proof outline on p.153: <math>\lambda\mbox{-definable}</math> <math>\stackrel{triv}{\implies}</math> <math>\lambda\mbox{-}K\mbox{-definable}</math> <math>\stackrel{160}{\implies}</math> <math>\mbox{Turing computable}</math> <math>\stackrel{161}{\implies}</math> <math>\mu\mbox{-recursive}</math> <math>\stackrel{Kleene}{\implies}</math><ref>{{cite journal | url=https://projecteuclid.org/euclid.dmj/1077489488 |first=Stephen C. |last=Kleene | author-link=Stephen C. Kleene | title=λ-definability and recursiveness | journal=Duke Mathematical Journal | volume=2 | number=2 | pages=340–352 |year=1936 | doi=10.1215/s0012-7094-36-00227-2}}</ref> <math>\lambda\mbox{-definable}</math>}} (this is one of the theorems that supports the [[Church–Turing thesis]]).  The μ-recursive functions are closely related to [[Primitive recursive function|primitive recursive function]]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&mdash;the most famous example is the [[Ackermann function]].

Other equivalent classes of functions are the functions of [[Lambda calculus|lambda calculus]] and the functions that can be computed by [[Markov algorithm]]s.

The subset of all ''total'' recursive functions with values in {{math|{{mset|0,1}}}} is known in [[Computational complexity theory|computational complexity theory]] as the [[R (complexity)|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 [[Μ operator|minimization operator {{mvar|μ}}]].

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, and to be non-primitive.

Primitive or "basic" functions:
#''Constant functions {{mvar|C{{su|b=n|p=k}}}}'': For each natural number {{mvar|n}} and every {{mvar|k}}
#::<math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>
#: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:''
#::<math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1\,</math>
# ''Projection function'' <math>P_i^k</math> (also called the ''Identity function''): For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>:
#::<math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i \, .</math>

Operators (the [[Domain of a function|domain of a function]] 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'' <math>\circ\,</math> (also called the ''substitution operator''): Given an m-ary function <math>h(x_1,\ldots,x_m)\,</math> and m k-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>:
#::<math>h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\  f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)).</math>
#:This means that <math>f(x_1,\ldots,x_k)</math> is defined only if <math>g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k),</math> and <math>h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math> are all defined.
# ''Primitive recursion operator'' {{mvar|&rho;}}: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and ''k''+2 -ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:
#::<math>\begin{align} 
             \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\  f \quad\text{where the k+1 -ary function } f \text{ is defined by}\\
    f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\
  f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)\,.\end{align}</math>
#:This means that <math>f(y,x_1,\ldots,x_k)</math> is defined only if <math>g(x_1,\ldots,x_k)</math> and <math>h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k)</math> are defined for all <math>z<y.</math>
#''Minimization operator''  {{mvar|&mu;}}: Given a (''k''+1)-ary function <math>f(y, x_1, \ldots, x_k)\,</math>, the ''k''-ary function <math>\mu(f)</math> is defined by:
#::<math>\begin{align}
          \mu(f)(x_1, \ldots, x_k) = z \stackrel{\mathrm{def}}{\iff}\ f(i, x_1, \ldots, x_k)&>0 \quad \text{for}\quad i=0, \ldots, z-1 \quad\text{and}\\
         f(z, x_1, \ldots, x_k)&=0\quad
\end{align}</math>
Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which {{mvar|f}} is not defined, then the search never terminates, and <math> \mu(f)</math> is not defined for the argument <math>(x_1, \ldots, x_k).</math>

While some textbooks use the μ-operator as defined here,<ref name="Enderton.1972">Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972</ref><ref name="Boolos.Burgess.Jeffrey.2007">Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007</ref> others like<ref name="Jones.1997">Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997</ref><ref>Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982</ref> demand that the μ-operator is applied to ''total'' functions {{mvar|f}} only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form Theorem (see below).<ref name="Enderton.1972"/><ref name="Boolos.Burgess.Jeffrey.2007"/> The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total.<ref name="Jones.1997"/>

The ''strong equality'' operator <math>\simeq</math> can be used to compare partial μ-recursive functions.  This is defined for all partial functions ''f'' and ''g'' so that
:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math> 
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.

==Examples==
Examples not involving the minimization operator can be found at [[Primitive recursive function]].

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.
{{unordered list
|The [[Integer square root|integer square root]] of {{mvar|x}} can be defined as the least {{mvar|z}} such that <math>(z+1)^2 > x</math>. Using the minimization operator, a general recursive definition is <math>\operatorname{Isqrt} = \mu(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2))</math>, where {{math|Not}}, {{math|Gt}}, and {{math|Mul}} are logical negation, greater-than, and multiplication,<ref>defined in [[Primitive recursive function]], [[Primitive recursive function]], and [[Primitive recursive function]]</ref> respectively. In fact, <math>(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2)) \; (z,x) = (\lnot S(z)*S(z) > x)</math> is {{val|0}} if, and only if, <math>S(z)*S(z) > x</math> holds. Hence <math>\operatorname{Isqrt}(x)</math> is the least {{mvar|z}} such that <math>S(z)*S(z) > x</math> holds. The negation [[Engineering:Junctor|junctor]] {{math|Not}} is needed since {{math|Gt}} encodes truth by {{val|1}}, while {{mvar|&mu;}} seeks for {{val|0}}.
}}
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
{{unordered list
|{{example needed|date=November 2021}}
}}

== 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]]''.

== Equivalence with other models of computability ==


In the equivalence of models of computability, a parallel is drawn between [[Turing machine]]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 [[Kleene's T predicate#Normal form theorem|normal form theorem]] due to Kleene says that for each ''k'' there are primitive recursive functions <math>U(y)\!</math> and <math>T(y,e,x_1,\ldots,x_k)\!</math> such that for any μ-recursive function <math>f(x_1,\ldots,x_k)\!</math> with ''k'' free variables there is an ''e'' such that
:<math>f(x_1,\ldots,x_k) \simeq U(\mu(T)(e,x_1,\ldots,x_k))</math>.
The number ''e'' is called an ''index'' or ''Gödel number'' for the function ''f''.<ref>{{cite journal | doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf | author=Stephen Cole Kleene | title=Recursive predicates and quantifiers | journal=Transactions of the American Mathematical Society | volume=53 | number=1 | pages=41&ndash;73 | date=Jan 1943 | doi-access=free }}</ref>{{rp|52–53}}  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.

[[Biography:Marvin Minsky|Minsky]] observes the <math>U</math> defined above is in essence the μ-recursive equivalent of the [[Universal Turing machine|universal Turing machine]]:
{{blockquote |text=To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, ''and essentially the same ideas'', as we have invested in constructing the universal Turing machine {{sfn|Minsky|1972|pp=189}}}}

== 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<sub>1</sub>, ..., x<sub>n</sub> is abbreviated as '''x''':
* ''Constant function'': Kleene uses " C{{su|b=q|p=n}}('''x''') = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " const<sub>n</sub>( '''x''') = n ": 
:: e.g. C{{su|b=13|p=7}} ( r, s, t, u, v, w, x ) = 13
:: e.g. const<sub>13</sub> ( 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 =<sub>def</sub> a', where 1 =<sub>def</sub>  0', 2 =<sub>def</sub> 0 ' ', etc.

* ''Identity function'': Kleene (1952) uses " U{{su|b=i|p=n}} " to indicate the identity function over the variables x<sub>i</sub>; B-B-J use the identity function id{{su|b=i|p=n}} over the variables x<sub>1</sub> to x<sub>n</sub>:
: U{{su|b=i|p=n}}( '''x''' ) = id{{su|b=i|p=n}}( '''x''' ) = x<sub>i</sub> 
: e.g. U{{su|b=3|p=7}} = id{{su|b=3|p=7}} ( r, s, t, u, v, w, x ) = t

* ''Composition (Substitution) operator'': Kleene uses a bold-face '''S'''{{su|b=n|p=m}} (not to be confused with his S for "successor" '''!''' ). The superscript "m" refers to the m<sup>th</sup> of function "f<sub>m</sub>", whereas the subscript "n" refers to the n<sup>th</sup> variable "x<sub>n</sub>":
:If we are given h( '''x''' )= g( f<sub>1</sub>('''x'''), ... , f<sub>m</sub>('''x''') )
::  h('''x''') = '''S'''{{su|b=m|p=n}}(g, f<sub>1</sub>, ... , f<sub>m</sub> )

:In a similar manner, but without the sub- and superscripts, B-B-J write: 
:: h(''x''')= Cn[g, f<sub>1</sub> ,..., f<sub>m</sub>]('''x''')

* ''Primitive Recursion'': Kleene uses the symbol " '''R'''<sup>n</sup>(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{{su|b=1|p=1}}(a)
::* induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U{{su|b=2|p=3}}( b, c, a ))
::: R<sup>2</sup> { U{{su|b=1|p=1}}(a), S [ (U{{su|b=2|p=3}}( b, c, a ) ] }
::: Pr{ U{{su|b=1|p=1}}(a), S[ (U{{su|b=2|p=3}}( b, c, a ) ] }

''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{{su|b=1|p=1}}(a) = a
:# U{{su|b=2|p=3}}( b, c, a ) = c
:# g(b, c, a) = S(U{{su|b=2|p=3}}( b, c, a )) = c'
:# base step: h( 0, a ) = U{{su|b=1|p=1}}(a)
:: induction step: h( b', a ) = g( b, h( b, a ), a )

He arrives at:
:: a+b = '''R'''<sup>2</sup>[ U{{su|b=1|p=1}}, '''S'''{{su|b=1|p=3}}(S, U{{su|b=2|p=3}}) ]

==Examples==
* [[Fibonacci number]]
* [[McCarthy 91 function]]

==See also==
*Recursion theory
* [[Recursion]]
* [[Recursion (computer science)]]

== References ==
{{Reflist}}
{{Refbegin}}
*{{cite book |first=Stephen |last=Kleene |title=Introduction to Metamathematics |publisher=Walters-Noordhoff & North-Holland |orig-year=1952 |year=1991 |isbn=0-7204-2103-9 }} 
*{{cite book |first=R. |last=Soare |title=Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets |publisher=Springer-Verlag |orig-year=1987 |year=1999 |isbn=9783540152996 |url=https://books.google.com/books?id=9I7Pl00LU5gC&pg=PP1}}
*{{cite book|first=Marvin L. |last=Minsky  |title=Computation: Finite and Infinite Machines |publisher=Prentice-Hall |orig-year=1967 |year=1972 |pages=210–5 |isbn=9780131654495}}
:On pages 210-215 Minsky shows how to create the μ-operator using the [[Register machine|register machine]] model, thus demonstrating its equivalence to the general recursive functions.
*{{cite book |first1=George |last1=Boolos |first2=John |last2=Burgess |first3=Richard |last3=Jeffrey |title=Computability and Logic |publisher=Cambridge University Press |edition=4th |year=2002 |isbn=9780521007580 |pages=70–71 |chapter=6.2 Minimization |chapter-url=https://books.google.com/books?id=0LpsXQV2kXAC&pg=PA70}}
{{Refend}}

==External links==
*[http://plato.stanford.edu/entries/recursive-functions/ Stanford Encyclopedia of Philosophy entry]
*[http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/ A compiler for transforming a recursive function into an equivalent Turing machine]


{{DEFAULTSORT:Mu-Recursive Function}}
[[Category:Computability theory]]
[[Category:Theory of computation]]

ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция

{{Sourceattribution|General recursive function}}