Kleene's recursion theorem: Difference between revisions

Revision as of 20:08, 17 January 2020

Revision as of 07:03, 6 May 2020

Line 138:

== Generalized theorem ==

[[AnatolyIn Maltsev]]the provedcontext aof generalizedhis versiontheory of thenumberings, [[Yury Yershov|Ershov]] showed that Kleene's recursion theorem holds for any set with a [[precomplete numbering]]{{Citation needed([[#CITEREFBarendregtTerwijn2019|date=OctoberBarendregt 2013}}& Terwijn 2019]], p. 1151). A Gödel numbering is a precomplete numbering on the set of computable functions so the generalized theorem yields the Kleene recursion theorem as a special case (for an English survey see [[#CITEREFErshov1999|Ershov 1999]], pp. 473{{ndash}}503).

Given a precomplete numbering <math>\nu</math> then for any partial computable function <math>f</math> with two parameters there exists a total computable function <math>t</math> with one parameter such that

Line 149:

== References ==

* {{Cite journal|last1=Barendregt|first1=Henk|author-link1=Henk Barendregt|last2=Terwijn|first2=Sebastiaan A.|date=1 October 2019|title=Fixed point theorems for precomplete numberings|url=http://www.sciencedirect.com/science/article/pii/S016800721930048X|journal=Annals of Pure and Applied Logic|language=English|volume=170|issue=10|pages=1151{{ndash}}1161|doi=10.1016/j.apal.2019.04.013|issn=0168-0072}}

* Cutland, N.J., 1980, ''Computability: An introduction to recursive function theory'', Cambridge University Press. {{isbn|0-521-29465-7}}

* {{Cite book|last=Ershov|first=Yuri L|author-link=Yury Yershov|editor-last=Griffor|editor-first=Edward R|url=https://books.google.com/books?id=KqeXZ4pPd5QC|title=Handbook of Computability Theory|chapter=Part 4: Mathematics and Computability Theory. 14. Theory of numbering|series=Studies in logic and the foundations of mathemtics|date=1999|volume=140|pages=473{{ndash}}503|publisher=[[Elsevier]]|isbn=978-0-444-89882-1|___location=Amsterdam|language=English|oclc=162130533}}

* [[Stephen Cole Kleene|Kleene, S.C.]], 1938, "[http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Kleene%20-%20Ordinals.pdf On Notation for Ordinal Numbers]", [[Journal of Symbolic Logic]] 3, 150–155.

* Kleene, S.C., 1952, ''Introduction to Metamathematics'', North-Holland. {{isbn|0-7204-2103-9}}

* [[Carl Jockusch|Jockusch, C.G. Jr.]]; Lerman, M.; Soare, R.I.; and Solovay, R.M., 1989, "Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion", [[Journal of Symbolic Logic]], 4, 1288&ndash;1323.