Smn Theorem and Stephen Cole Kleene

Published by Reblogs - Credits in Posts,



Near Matches Ignore ExactFull Text

Smn Theorem (idea)

See all of Smn Theorem, no other writeups in this node.
(idea) by dido Sun Sep 28 2003 at 5:20:53

The Smn 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 Smn theorem states that for every m, n ≥ 1, there exists a total recursive function Smn : Nm+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)(xm+1, ... xm+n) = φe(x1, ..., xm+n)

where φe denotes the TM with description number e.

An important corollary of the Smn theorem states that for every partial recursive function ψ(e, x) there exists a total recursive function f such that φf(e)(x) = ψ(e, x).

Everything2 ™ is brought to you by Everything2 Media, LLC. All content copyright © original author unless stated otherwise.