General recursive function: Difference between revisions

Revision as of 12:29, 5 March 2025

Latest revision as of 19:37, 29 July 2025

(3 intermediate revisions by 3 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 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 42:

The ''[[strong equality]]'' relation <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 70:

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