Kleene's recursion theorem: Difference between revisions

Revision as of 17:53, 3 August 2021

Revision as of 22:29, 12 February 2022

Line 1:

{{distinguish|text=[[Kleene's theorem]] for regular languages}}

{{Use shortened footnotes|date=May 2021}}

In [[computability theory]], '''Kleene's recursion theorems''' are a pair of fundamental results about the application of [[computable function]]s to their own descriptions. The theorems were first proved by [[Stephen Cole Kleene|Stephen Kleene]] in 1938{{r|Kleene1938}} and appear in his 1952 book ''Introduction to Metamathematics''.{{sfn|Kleene|1952}} A related theorem, which constructs fixed points of a computable function, is known as '''Rogers's theorem''' and is due to [[Hartley Rogers, Jr.]].{{sfn|Rogers|1967}}

The recursion theorems can be applied to construct [[fixed point (mathematics)|fixed points]] of certain operations on [[computable function]]s, to generate [[quine (computing)|quines]], and to construct functions defined via [[recursive definition]]s.

Line 142:

== References ==

* {{Cite book |last=Ershov |first=Yuri L. |author-link=Yury Yershov |date=1999 |chapter=Part 4: Mathematics and Computability Theory. 14. Theory of numbering |editor-last=Griffor |editor-first=Edward R. |title=Handbook of Computability Theory |series=Studies in logic and the foundations of mathematics |volume=140 |___location=Amsterdam |publisher=[[Elsevier]] |pp=473-503473–503 |isbn=9780444898821 |oclc=162130533 |access-date=6 May 2020 |url=https://books.google.com/books?id=KqeXZ4pPd5QC

}}

* {{Cite book |last=Jones |first=Neil D. |author-link=Neil D. Jones |date=1997 |title=Computability and complexity: From a Programming Perspective |___location=[[Cambridge, Massachusetts]] |publisher=[[MIT Press]] |isbn=9780262100649 |oclc=981293265

Line 152:

'''Footnotes'''

{{reflist|refs=

<ref name=Kleene1938>{{Cite journal |last=Kleene |first=Stephen C. |author-link=Stephen Cole Kleene |date=1938 |title=On notation for ordinal numbers |journal=[[Journal of Symbolic Logic]] |volume=3 |issue=4 |pp=150-155150–155 |issn=0022-4812 |doi=10.2307/2267778 |jstor=2267778 |access-date=6 May 2020 |url=http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Kleene%20-%20Ordinals.pdf}}</ref>

<ref name=Soare1987_88>{{Cite book |last=Soare |first=R.I. |author-link=Robert I. Soare |date=1987 |title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|series=Perspectives in Mathematical Logic |___location=Berlin and New York City |publisher=[[Springer-Verlag]] |p=88 |isbn=9780387152998 |oclc=318368332}}</ref>

Line 158:

<ref name=Cutland1980_204>{{Cite book |last=Cutland |first=Nigel J. |author-link=Nigel Cutland |date=1980 |title=Computability: An Introduction to Recursive Function Theory |publisher=[[Cambridge University Press]] |at=[https://books.google.com/books?id=wAstOUE36kcC&pg=PA204 p. 204] |isbn=9781139935609 |doi=10.1017/cbo9781139171496 |oclc=488175597 |access-date=6 May 2020 |url=https://books.google.com/books?id=wAstOUE36kcC}}</ref>

<ref name=BarendregtTerwijn2019_1151>{{Cite journal |last1=Barendregt |first1=Henk |author-link1=Henk Barendregt |last2=Terwijn |first2=Sebastiaan A. |date=2019 |title=Fixed point theorems for precomplete numberings |journal=Annals of Pure and Applied Logic |volume=170 |issue=10 |pp=1151-11611151–1161 |issn=0168-0072 |doi=10.1016/j.apal.2019.04.013 |hdl=2066/205967 |hdl-access=free |s2cid=52289429 |access-date=6 May 2020 |url-access=subscription |url=http://www.sciencedirect.com/science/article/pii/S016800721930048X }} p. 1151.</ref>

}}

==Further reading==

* {{Cite journal |last1=Jockusch |first1=C. G. |author-link1=Carl Jockusch |last2=Lerman |first2=M. |last3=Soare |first3=R.I. |author-link3=Robert I. Soare |last4=Solovay |first4=R.M. |author-link4=Robert M. Solovay |date=1989 |title=Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion |journal=[[The Journal of Symbolic Logic]] |volume=54 |issue=4 |pp=1288-13231288–1323 |issn=0022-4812 |doi=10.1017/S0022481200041104 |jstor=2274816}}

== External links ==