S^m_n theorem

In computability theory the S m
n  theorem, written also as "smn-theorem" or "s-m-n theorem" (also called the translation lemma, parameter theorem, and the parameterization theorem) is a basic result about programming languages (and, more generally, Gödel numberings of the partial computable functions) (Soare 1987, Rogers 1967). It was first proved by Stephen Cole Kleene (1943). The name ${\displaystyle S_{m}^{n}}$ comes from the occurrence of an ${\displaystyle S}$ with subscript ${\displaystyle n}$ and superscript ${\displaystyle m}$ in the original formulation of the theorem (see below).

In practical terms, the theorem says that for a given programming language and positive integers ${\displaystyle m}$ and ${\displaystyle n}$, there exists a particular algorithm that accepts as input the source code of a program with ${\displaystyle m+n}$ free variables, together with ${\displaystyle m}$ values. This algorithm generates source code that in essence substitutes the values for the first ${\displaystyle m}$ free variables, leaving the rest of the variables free.