General recursive function: Difference between revisions

Revision as of 13:55, 23 June 2021

Revision as of 14:44, 31 August 2021

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. If the function is total, it is also called a '''total recursive function''' (sometimes shortened to '''recursive function''').<ref>https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC</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 }} 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]].

Line 102:

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

Line 109:

: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 |first=George |last=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}}