Smn theorem
On transforming a program by substituting constants for free variables / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Smn theorem?
Summarize this article for a 10 year old
In computability theory the S m
n theorem, written also as "smn-theorem" or "s-m-n theorem" (also called the translation lemma, parameter theorem, and the parameterization theorem) is a basic result about programming languages (and, more generally, Gödel numberings of the computable functions) (Soare 1987, Rogers 1967). It was first proved by Stephen Cole Kleene (1943). The name S m
n comes from the occurrence of an S with subscript n and superscript m in the original formulation of the theorem (see below).
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. This algorithm generates source code that effectively substitutes the values for the first m free variables, leaving the rest of the variables free.
The smn-theorem states that given a function of two arguments which is computable, there exists a total and computable function such that basically "fixing" the first argument of . It's like partially applying an argument to a function. This is generalized over tuples for . In other words,it addresses the idea of "parametrization" or "indexing" of computable functions. It's like creating a simplified version of a function that takes an additional parameter (index) to mimic the behavior of a more complex function.
The function is designed to mimic the behavior of when given the appropriate parameters. Essentially, by selecting the right values for and , you can make behave like for a specific computation. Instead of dealing with the complexity of , we can work with a simpler that captures the essence of the computation.