# Smn Theorem and Stephen Cole Kleene

Published by Reblogs - Credits in Posts,

# Smn Theorem (idea)

The *S*_{mn} theorem, also known as the iteration theorem, was first proved by Stephen Cole Kleene, and provides the theoretical justification for use of currying functions (or partial evaluation) in the lambda calculus, here presented in terms of Turing machines. It basically states that if we have some a Turing machine that computes some partial recursive function of *m* + *n* variables, we can effectively construct another Turing machine that holds *m* of these variables fixed, so when *n* more variables are applied, the value of the original function can be calculated.

Formally, the *S*_{mn} theorem states that for every *m, n* ≥ 1, there exists a total recursive function *S _{mn}* :

*N*

^{m+1}→

*N*, such that for some Turing machine description number

*e*that denotes a TM calculating a partial recursive function of

*m*+

*n*variables, we have:

φ_{Smn(e, x1, ... xm)}(x_{m+1}, ... x_{m+n}) = φ_{e}(x_{1}, ..., x_{m+n})

where φ_{e} denotes the TM with description number *e*.

An important corollary of the *S _{mn}* theorem states that for every partial recursive function ψ(e, x) there exists a total recursive function

*f*such that φ

_{f(e)}(x) = ψ(e, x).

## Sign in

## Recommended Reading

## New Writeups

- How To Be Good(personal) by CycloneE2
- Live in Fear(personal) by brick killed u
- the smoke of our burned books rises into the sky(poetry) by etouffee
- slow dancing with myself(poetry) by ame_9001
- Pitiful Still and Eyes Big As Moons(fiction) by lostcauser
- A jaundiced look at Everything2 Kansas(log) by seagulltheme
- August 20, 2023(event) by JD
- Pop(recipe) by seagulltheme
- What do you remember?(personal) by AsteroidPuncher
- bird-songs for millennia(thing) by etouffee