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…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.