Smn theorem

Remarks

The program $s^m_n(e, \bar x)$ first writes the fixed numbers $\bar x$ in front of its input $\bar y$, then runs program $e$. Building this program from $e$ and $\bar x$ is a simple manipulation of codes, so $s^m_n$ is primitive recursive.

Example: let $e$ be a program for $(x, y) \mapsto x + y$. Then $s^1_1(e, 5)$ is the number of a program for $y \mapsto 5 + y$, and $x \mapsto s^1_1(e, x)$ computes an index for "add $x$" from $x$.

The theorem is also called the parameter theorem, and it is due to Kleene.

Going deeper

For a student

The smn theorem is used to turn a construction "uniform in a parameter" into a computable function on indices. It is the main tool in the proof of Kleene's recursion theorem. It is also used to build many-one reductions, for example in the proof of Rice's theorem. Numberings that satisfy the smn theorem and have a universal function are called acceptable, and any two of them are computably isomorphic by a theorem of Rogers.