Smn theorem
In computability theory the 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…
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computability theory the 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 S^m_n comes from the occurrence of an S with subscript n and superscript 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 m and n , there exists a particular algorithm that accepts as input the source code of a program with m + n free variables, together with m values.
This algorithm generates source code that in essence substitutes the values for the first m free variables, leaving the rest of the variables free.
Details
The basic form of the theorem applies to functions of two arguments (Nies 2009, p. 6). Given a Gödel numbering \varphi of partial computable functions, there is a primitive recursive function s of two arguments with the following property: for every Gödel number e of a partial computable function f with two arguments, the expressions \varphi_{s(e, x)}(y) and f(x, y) are defined for the same combinations of natural numbers x and y , and their values are equal for any such combination.
In other words, the following extensional equality of functions holds for every x : \varphi_{s(e, x)} \simeq \lambda y.\varphi_e(x, y). More generally, for any m, n > 0 , there exists a primitive recursive function S^m_n of m + 1 arguments that behaves as follows: for every Gödel number e of a partial computable function with m + n arguments, and all values of x_1, x_2, ..., x_m : \varphi_{S^m_n(e, x_1, \dots, x_m)} \simeq \lambda y_1, \dots, y_n.\varphi_e(x_1, \dots, x_m, y_1, \dots, y_n). The function s described above can be taken to be S^1_1 .
Formal statement
Given arities m and n , for every Turing Machine \text{TM}_x of arity m + n and for all possible values of inputs y_1, \dots, y_m , there exists a Turing machine \text{TM}_k of arity n , such that \forall z_1, \dots, z_n : \text{TM}_x(y_1, \dots, y_m, z_1, \dots, z_n) = \text{TM}_k(z_1, \dots, z_n). Furthermore, there is a Turing machine S that allows k to be calculated from x and y ; it is denoted k = S_n^m(x, y_1, \dots, y_m) . Informally, S finds the Turing Machine \text{TM}_k that is the result of hardcoding the values of y into \text{TM}_x . The result generalizes to any Turing-complete computing model.
Example
The following Lisp code implements s 11 for Lisp. (defun s11 (f x) (let ((y (gensym))) (list 'lambda (list y) (list f x y)))) For example, evaluates to , where is a "fresh" symbol.
See also
Currying Kleene's recursion theorem Partial evaluation
References
(This is the reference that the 1989 edition of Odifreddi's "Classical Recursion Theory" gives on p. 131 for the S^m_n theorem.)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378480647 under CC BY-SA 4.0; modifications have been made.