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 Sources
1. Wikipedia: Smn theorem
WikipediaLead section, statement-form referenceQuote, Lead 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.
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.