# Smn theorem

The -theorem is a central result of the computability theory . It represents a tool in computer science with which the code of a program can be calculated depending on parameters, and was first proven by Stephen C. Kleene (see recursion theorem ). A result of this is that a programming language that can execute code generated at runtime can support currying . ${\ displaystyle s_ {n} ^ {m}}$

## Formal definition

Let an effective numbering of all partially calculable functions (e.g. the Gödel numbering of all deterministic Turing machines ) be. ${\ displaystyle \ {\ varphi _ {i} \} _ {i \ in \ mathbb {N}}}$

Assuming that the corresponding function is of the type for a fixed index , there is a total and computable function with ${\ displaystyle i}$${\ displaystyle \ varphi _ {i} \ colon \ mathbb {N} ^ {m + n} \ to \ mathbb {N}}$${\ displaystyle s_ {n} ^ {m} \ colon \ mathbb {N} ^ {m + 1} \ to \ mathbb {N}}$

${\ displaystyle \ varphi _ {s_ {n} ^ {m} (i, y_ {1}, ..., y_ {m})} (z_ {1}, ..., z_ {n}) = \ varphi _ {i} (y_ {1}, ..., y_ {m}, z_ {1}, ..., z_ {n})}$for everyone .${\ displaystyle (y_ {1}, ..., y_ {m}, z_ {1}, ..., z_ {n}) \ in \ mathbb {N} ^ {m + n}}$

## Non-formal declaration

The property says that there is a code that is executed (or can be executed) with the parameters and , a transformation program that outputs , and a program that calculates the same on input as it does on input from and . ${\ displaystyle s_ {n} ^ {m}}$${\ displaystyle w}$${\ displaystyle x}$${\ displaystyle v}$${\ displaystyle U}$${\ displaystyle w}$${\ displaystyle x}$${\ displaystyle v}$${\ displaystyle w_ {x}}$${\ displaystyle v}$${\ displaystyle w}$${\ displaystyle x}$${\ displaystyle v}$

## Examples

The -theorem is a possibility to construct new functions from functions whose predictability is already known. ${\ displaystyle s_ {n} ^ {m}}$

For example, let to show that a total and computable function exists, so for the following applies: . ${\ displaystyle g \ colon \ mathbb {N} ^ {2} \ to \ mathbb {N}}$${\ displaystyle i, j, x \ in \ mathbb {N}}$${\ displaystyle \ varphi _ {g (i, j)} (x) = \ varphi _ {i} (x) + \ varphi _ {j} (x)}$

To do this, define . The function can be calculated, so there is an index , such that: . From the -Theorem the existence of a total computable function now follows with for all . Now we define , is then obviously also totally calculable and the following applies: ${\ displaystyle \ psi (i, j, x) = \ varphi _ {i} (x) + \ varphi _ {j} (x)}$${\ displaystyle \ psi}$${\ displaystyle k \ in \ mathbb {N}}$${\ displaystyle \ psi = \ varphi _ {k}}$${\ displaystyle s_ {n} ^ {m}}$${\ displaystyle s_ {1} ^ {2} \ colon \ mathbb {N} ^ {3} \ to \ mathbb {N}}$${\ displaystyle \ varphi _ {s_ {1} ^ {2} (k, i, j)} (x) = \ varphi _ {k} (i, j, x) = \ psi (i, j, x) }$${\ displaystyle i, j, x \ in \ mathbb {N}}$${\ displaystyle g (i, j): = s_ {1} ^ {2} (k, i, j)}$${\ displaystyle g}$

${\ displaystyle \ varphi _ {g (i, j)} (x) = \ varphi _ {s_ {1} ^ {2} (k, i, j)} (x) = \ psi (i, j, x ) = \ varphi _ {i} (x) + \ varphi _ {j} (x)}$

In particular, the theorem is often used to construct reduction functions : ${\ displaystyle s_ {n} ^ {m}}$

As an example, the general holding problem should be reduced to the epsilon holding problem . More precisely, so the existence of a total computable function to show, so for all true . ${\ displaystyle H = \ {(i, x) \ in \ mathbb {N} ^ {2} \ mid \ varphi _ {i} (x) {\ downarrow} \}}$${\ displaystyle H_ {0} = \ {e \ in \ mathbb {N} \ mid \ varphi _ {e} (0) {\ downarrow} \}}$${\ displaystyle f \ colon \ mathbb {N} ^ {2} \ to \ mathbb {N}}$${\ displaystyle i, x \ in \ mathbb {N}}$${\ displaystyle \ varphi _ {i} (x) {\ downarrow} \ Leftrightarrow \ varphi _ {f (i, x)} (0) {\ downarrow}}$

Analogous to the above one defines that the function is obviously calculable and its value does not depend on . So let it be an index so that . The -theorem now yields the existence of a totally computable function , so that . If you sit down and choose , it results ${\ displaystyle \ psi (i, x, y) = \ varphi _ {i} (x)}$${\ displaystyle \ psi}$${\ displaystyle y}$${\ displaystyle k}$${\ displaystyle \ psi = \ varphi _ {k}}$${\ displaystyle s_ {n} ^ {m}}$${\ displaystyle s_ {1} ^ {2}}$${\ displaystyle \ varphi _ {s_ {1} ^ {2} (k, i, x)} (y) = \ varphi _ {k} (i, x, y)}$${\ displaystyle f (i, x) = s_ {1} ^ {2} (k, i, x)}$${\ displaystyle y = 0}$

${\ displaystyle \ varphi _ {f (i, x)} (0) = \ varphi _ {k} (i, x, 0) = \ psi (i, x, 0) = \ varphi _ {i} (x ).}$