Theorem

Kleene's Recursion Theorem

Logic and Foundations

Kleene's Recursion Theorem states that for any computable function that transforms one program into another, there exists a program that computes the same function as the program it is transformed into, so that every such transformation has a fixed point among the programs. Named for Stephen Kleene, it is a foundational result of computability theory underlying self-referential constructions such as programs that access and act on their own source code.

Facts

Statement

For any partial recursive function Q of two arguments there is an index p such that the partial recursive function computed by program p is equivalent to the function sending y to Q(p, y), so a self-referential program can always be constructed for a given task. 1

Proof Year

1938 1

Classification

Statement Form

Existence Theorem 1

Connections

Has Statement Form

Existence Theorem

Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.

In Branch

Computability Theory

Source Kleene's Recursion Theorem (Wikipedia)

Proved By

Stephen Cole Kleene

Source Kleene's Recursion Theorem (Wikipedia)

Sources

1. Kleene's Recursion Theorem (Wikipedia)

Wikimedia Foundation

Kleene's second recursion theorem section
One informal interpretation of the second recursion theorem is that it is possible to construct self-referential programs
lead section, second sentence
The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics.
In Branch: Computability Theory, Lead sentence
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functio
Proved By: Stephen Cole Kleene, Lead paragraph
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions.

Switch Atlas

The Inner World

The Civil World

The Natural World

Kleene's Recursion Theorem

Has Statement Form

In Branch

Proved By