Smn theorem

In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a> the S mn  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 <a href="/facts/Programming_language/cWTYbgWa">programming languages</a> (and, more generally, <a href="/facts/G%C3%B6del_numbering/36BpTK1g">Gödel numberings</a> of the <a href="/facts/Computable_function/dzwBlLGn">computable functions</a>) (Soare 1987, Rogers 1967). It was first proved by <a href="/facts/Stephen_Cole_Kleene/sKSax2se">Stephen Cole Kleene</a> (1943). The name S mn  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 <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that accepts as input the <a href="/facts/Source_code/o9J6Jv23">source code</a> of a program with m + n <a href="/facts/Free_variables/ndWnXXYs">free variables</a>, together with m values. This algorithm generates source code that effectively substitutes the values for the first m free variables, leaving the rest of the variables free.
The smn-theorem states that given a function of two arguments 
 
 
 
 g
 (
 x
 ,
 y
 )
 
 
 {\displaystyle g(x,y)}
 
 which is <a href="/facts/Computable_function/dzwBlLGn">computable</a>, there exists a <a href="/facts/Total_function/0vJMw0Nm">total</a> and computable function such that 
 
 
 
 
 ϕ
 
 s
 
 
 (
 x
 )
 (
 y
 )
 =
 g
 (
 x
 ,
 y
 )
 
 
 {\displaystyle \phi _{s}(x)(y)=g(x,y)}
 
 basically "fixing" the first argument of 
 
 
 
 g
 
 
 {\displaystyle g}
 
. It's like partially applying an argument to a function. This is generalized over 
 
 
 
 m
 ,
 n
 
 
 {\displaystyle m,n}
 
 tuples for 
 
 
 
 x
 ,
 y
 
 
 {\displaystyle x,y}
 
. In other words, it addresses the idea of "parameterization" or "indexing" of computable functions. It's like creating a simplified version of a function that takes an additional parameter (index) to mimic the behavior of a more complex function.
The function 
 
 
 
 
 s
 
 m
 
 
 n
 
 
 
 
 {\displaystyle s_{m}^{n}}
 
 is designed to mimic the behavior of 
 
 
 
 ϕ
 (
 x
 ,
 y
 )
 
 
 {\displaystyle \phi (x,y)}
 
 when given the appropriate parameters. Essentially, by selecting the right values for 
 
 
 
 m
 
 
 {\displaystyle m}
 
 and 
 
 
 
 n
 
 
 {\displaystyle n}
 
, you can make 
 
 
 
 s
 
 
 {\displaystyle s}
 
 behave like for a specific computation. Instead of dealing with the complexity of 
 
 
 
 ϕ
 (
 x
 ,
 y
 )
 
 
 {\displaystyle \phi (x,y)}
 
, we can work with a simpler 
 
 
 
 
 s
 
 m
 
 
 n
 
 
 
 
 {\displaystyle s_{m}^{n}}
 
 that captures the essence of the computation.

Smn theorem open-in-new

Smn theorem