General recursive function: Difference between revisions

Revision as of 07:09, 13 June 2022

Latest revision as of 19:37, 29 July 2025

(12 intermediate revisions by 11 users not shown)

Line 1:

{{Short 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.

Line 21:

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

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

Line 38:

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 [[#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]]'' 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==

Line 49:

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 {{mvarval|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.

Line 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|Minsky]] observes the <math>U</math> defined above is in essence the μ-recursive equivalent of the [[universal Turing machine]]:

Line 84:

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