General recursive function: Difference between revisions

Revision as of 01:31, 15 June 2022

Revision as of 10:22, 25 November 2022

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, 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}}</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.