Kleene's recursion theorem: Difference between revisions

Revision as of 22:41, 9 January 2018

Revision as of 16:35, 10 May 2018

Line 1:

{{distinguish2distinguish|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 ''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.]] (1967).