S-m-n theorem

The S-m-n theorem states that parameters of a partial computable function can be incorporated effectively into its program index. It formalizes specialization: a program can be transformed into one that has some inputs fixed in advance.

Partial computable function: A function computed by an algorithm that may fail to halt on some inputs. The theorem applies to these functions and transforms their indices when inputs are fixed.
Computable function: A function whose values can be produced by an algorithm that halts on every input. The theorem’s partial functions generalize this total, everywhere-defined case.
Stephen Cole Kleene: An American mathematician and logician who helped establish recursion theory and mathematical logic. Kleene formulated the parameter theorem as part of the foundations of recursive function theory.
Quines: Programs that produce their own source code or an equivalent representation when executed. Index self-reference can be assembled by combining the recursion theorem with effective parameterization.
s-m-n theorem in recursion theory: A general theorem that computable functions can be specialized by fixing selected arguments effectively. This is the broader parameterization principle commonly named the parameter theorem.
Gödel numbering: An effective assignment of natural-number codes to formal expressions or computational objects. The theorem operates on program indices supplied by an effective coding.
Program index: A natural number identifying a program in a fixed effective enumeration of programs. The theorem transforms an index to encode fixed values of selected inputs.
Recursive function theory: The study of functions defined by effective computation and their formal properties. The S-m-n theorem arose as a central structural result in this field.
Universal partial computable function: A partial computable function that simulates every partial computable function from its program index. The theorem applies directly to indices in universal enumerations of partial computable functions.
Rice–Shapiro theorem: A characterization of which extensional properties of computably enumerable sets are semidecidable. It studies detectable semantic properties, unlike the S-m-n theorem’s construction of indices.

Linked from 1 page