General recursive function: Difference between revisions

Revision as of 13:55, 23 June 2021

Latest revision as of 19:37, 29 July 2025

(31 intermediate revisions by 17 users not shown)

Line 1:

{{shortShort description|One of several equivalent definitions of a computable function}}

In [[mathematical logic]] and [[computer science]], a '''general recursive function''', '''partial recursive function''', or '''μ-recursive function''' is a [[partial function]] from [[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 function|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 (computation)|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 | author-link=Alan 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| url-access=subscription }}</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]]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]] and the functions that can be computed by [[Markov algorithm]]s.

Line 8:

==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 <math>{{mvar|n\,</math>}} and every <math>{{mvar|k\,</math><br />&nbsp;&nbsp;&nbsp;&nbsp;}}
#::<math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n</math><br />
#:Alternative definitions use instead a '''zero function''' as a primitive function that always returns zero, and builtbuild the constant functions from the zero function, the successor function and the composition operator.

# '''Successor function S:'''<br />&nbsp;&nbsp;&nbsp;&nbsp;
#::<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>:<br />&nbsp;&nbsp;&nbsp;&nbsp;
#::<math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i \, .</math>

Operators (the [[___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>:<br />&nbsp;&nbsp;&nbsp;&nbsp;
#::<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><br />
#: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''' <math>\{{mvar|&rho\,</math>;}}: 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>:<br />&nbsp;&nbsp;&nbsp;&nbsp;
#::<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><br />
#: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''' <math>\ {{mvar|&mu\,</math>;}}: 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:<br />&nbsp;&nbsp;&nbsp;&nbsp;
#::<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>

\end{align}</math><br />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> <br> (''Note'': 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 <math>f</math> 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 [[#Normal form theorem|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"/>)

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>

\end{align}</math><br />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> <br> (''Note'': 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 <math>{{mvar|f</math>}} 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 [[#Normal form theorem|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

The '''[[strong equality']]'' operatorrelation <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#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.

{{unordered list

|The [[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#Junctors]], [[Primitive recursive function#Equality predicate]], and [[Primitive recursive function#Multiplication]]</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 [[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 ==

Line 45 ⟶ 69:

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 y\, (T)(y,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.

[[Marvin Minsky (1967)|Minsky]] observes (as does Boolos-Burgess-Jeffrey (2002) pp.&nbsp;94–95) that the <math>U</math> defined above is in essence the μ-recursive equivalent of the [[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. (italics in original, {{sfn|Minsky (1967) p. |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 we will abbreviate the string of parameters x₁, ..., x_n 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_n( '''x''') = n ":

:: e.g. C{{su|b=13|p=7}} ( r, s, t, u, v, w, x ) = 13

:: e.g. const₁₃ ( 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{{su|b=i|p=n}} " to indicate the [[identity function]] over the variables x_i; B-B-J use the identity function id{{su|b=i|p=n}} over the variables x₁ to x_n:

: U{{su|b=i|p=n}}( '''x''' ) = id{{su|b=i|p=n}}( '''x''' ) = x_i

: 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^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₁('''x'''), ... , f_m('''x''') )

:: h('''x''') = '''S'''{{su|b=m|p=n}}(g, f₁, ... , f_m )

Line 71 ⟶ 95:

:: h(''x''')= Cn[g, f₁ ,..., f_m]('''x''')

* '''Primitive Recursion''': Kleene uses the symbol " '''R'''ⁿ(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''' )

Line 81 ⟶ 105:

::: 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

Line 102 ⟶ 126:

== References ==

{{reflistReflist}}

{{refbeginRefbegin}}

*{{cite book |author-link=Stephen Kleene |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|author-link=Marvin L. Minsky |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]] model, thus demonstrating its equivalence to the general recursive functions.

*{{cite book |author-link=George Boolos |firstfirst1=George |lastlast1=Boolos |author2-link=John P. Burgess |first2=John |last2=Burgess |author3-link=Richard Jeffrey |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}}

{{refendRefend}}

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

{{Authority control}}

{{DEFAULTSORT:Mu-Recursive Function}}