Kleene's recursion theorem: Difference between revisions

Revision as of 00:30, 21 June 2020

Revision as of 22:52, 1 September 2020

Line 1:

{{Use Harvard referencing|date=August 2020}}

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

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 and appear in his 1952 book ''[[#CITEREFKleene1952|Introduction to Metamathematics]]''. A related theorem which constructs fixed points of a computable function is known as '''Rogers's theorem''' and is due to [[Hartley Rogers, Jr.]] {{harv|Rogers|1967}}.