The S-m-n Theorem, also called the parameter theorem, was proved by Stephen Cole Kleene in 1943 and is a foundational result of computability theory stating that for any programming language and any positive integers m and n there is a computable procedure that takes the source code of a program with m plus n free variables, together with values for the first m of them, and produces the source code of a new program with the remaining n variables free and the given values already substituted in. The theorem formalizes the idea that programs can be systematically specialized by fixing some of their inputs, and underlies later notions such as currying and partial evaluation in programming languages.
Facts
Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Wikipedia: Smn theorem
Proved By
Source Wikipedia: Smn theorem
Sources
1. Wikipedia: Smn theorem
WikipediaLead section, statement-form reference
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.
In Branch: Computability Theory, Lead sentence
In computability theory the S mn theorem, written also as "smn-theorem" or "s-m-n theorem" (also called the translation lemma, par
Proved By: Stephen Cole Kleene, Lead paragraph
of the partial computable functions) (Soare 1987, Rogers 1967). It was first proved by Stephen Cole Kleene (1943). The name
View the Source 2. S-m-n theorem, Wikipedia
Lead paragraph, attributionQuote, Lead paragraph, attribution
It was first proved by Stephen Cole Kleene (1943).
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.