✳flâneur — a map of the web's best reading

Kleene's recursion theorem - Wikipedia

en.wikipedia.org · 3,687 words · saved by 1 readers

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938[1] and appear in his 1952 book Introduction to Metamathematics.[2] A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.[3] The recursion theorems can be applied to construct fixed points of certain operations on computable functions, to generate quines, and to construct functions defined via recursive definitions. The statement of the theorems refers to an admissible numbering 𝜑 of the partial recursive functions, such that the function corresponding to index 𝑒 is 𝜑 𝑒 . If 𝐹 and 𝐺 are partial functions on the natural numbers, the notation 𝐹 ≃ 𝐺 indicates that, for each n, either 𝐹 ( 𝑛 ) and 𝐺 ( 𝑛 ) are both defined and are equal, or else 𝐹 ( 𝑛 ) and 𝐺 ( 𝑛

Kleene's recursion theorem - Wikipedia Jump to content From Wikipedia, the free encyclopedia Theorem in computability theory Not to be confused with Kleene's theorem for regular languages. In computability theory , Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 [ 1 ] and appear in his 1952 book Introduction to Metamathematics . [ 2 ] A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to H

Explore this link on the map →

related reading