Kleene's recursion theorem

A theorem in computability theory stating that every effective transformation of program descriptions has a fixed-point program whose behavior matches the transformed description.

Fixed-point theorem: A result guaranteeing an element that a function maps to itself. The theorem is a computability-specific fixed-point result, with equality understood through program behavior.
Quine (computing): A computer program that prints its own source code without reading its source file. The recursion theorem can construct quines by making a program reproduce its own description.
Computable function: A function that can be evaluated by an algorithm, possibly with nontermination when treated as a partial function. The theorem applies to effective transformations represented by computable operations on indices.
Banach fixed-point theorem: A theorem that gives a unique fixed point for a contraction on a complete metric space. Unlike Banach's theorem, this result concerns computable program behavior rather than metric convergence.
Acceptable numbering: An effective enumeration of partial computable functions that supports universal simulation and effective compilation. The theorem is stated over program indices in an enumeration with these effective properties.
Rice's theorem: A theorem stating that every nontrivial semantic property of partial computable functions is undecidable. Fixed-point reasoning provides a standard route to proving Rice-style undecidability results.
Partial computable function: A function computed by an algorithm that may fail to produce an output for some inputs. Program behavior in the theorem is compared as partial computable behavior.
Diagonal lemma: A formal logic result constructing a sentence equivalent to a formula applied to that sentence's name. Both results formalize self-reference, but the diagonal lemma concerns sentences and provability.
s-m-n theorem: A computability theorem that turns parameters of a computable function into parameters of its program index. Its parameterization operation supplies the machinery used to construct fixed-point indices.
Halting problem: The decision problem of determining whether an arbitrary program halts on a given input. Self-reference from the theorem supports diagonal arguments related to halting undecidability.

Linked from 4 pages

Self-referenceRelated: It gives a computational fixed-point result that supports programs referring to their own descriptions.