In computability theory the s_mn theorem, (also called the translation lemma or parameter theorem) is a basic result about programming languages, abstractly called Gödel numberings, first given by Stephen Cole Kleene. Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...

In practical terms, the theorem says that, given any programming language and integers m, n > 0, there is an algorithm with the following property: given the source code for a function with m + n arguments and values for the first m as input, it outputs the source code for a function that effectively hardcodes the first m arguments to those values. In mathematics, computing, linguistics and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... Source code (commonly just source or code) is any series of statements written in some human-readable computer programming language. ...

A corollary of the theorem is that any programming language capable of executing code generated at runtime can be made to support currying. In computer science, run time (with a space, though often its spelled without one) describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time). ... In computer science and linguistics (semantics), currying or Schönfinkelisation [1] is the technique of transforming a function that takes multiple arguments into a function that takes a single argument (the first of the arguments to the original function) and returns a new function that takes the remainder of the...

Details

The basic form of the theorem applies to functions of two arguments. Given a Gödel numbering φ of recursive functions, there is a primitive recursive function s of two arguments with the following property: for every Gödel number p of a function with two arguments, and p(x,y) are defined for the same combinations of x and y and equal for those combinations. In other words, the following extensional equality of functions holds: In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ... In mathematics, this usually refers to some form of the principle, going back to Leibniz, that two mathematical objects are equal if there is no test to distinguish them. ...

To generalize the theorem, choose a scheme for encoding n numbers as one number, so that the original numbers can be extracted by primitive recursive functions. For example, one might interleave the bits of the numbers. Then for any m,n > 0, there exists a primitive recursive function s_mn of m+1 arguments that behaves as follows: for every Gödel number p of a function with m+n arguments, A bit (binary digit) refers to a digit in the binary numeral system, which consists of base 2 digits (ie. ...

s₁₁ is just the function s already described.

Example

The following Lisp code implements s₁₁ for Lisp. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...

 (defun s11 (f x) (list 'lambda '(y) (list f x 'y)) 

For example, (s11 '(lambda (x y) (+ x y)) 3) evaluates to (lambda (y) ((lambda (x y) (+ x y)) 3 y)).

See also

• Kleene's recursion theorem

In computability theory Kleenes recursion theorem, first proved by Stephen Kleene in 1938, is a fundamental result about the application of computable functions to their own descriptions. ...

References

• Odifreddi, P. (1999). Classical Recursion Theory. North-Holland. ISBN 0-444-87295-7.
• Rogers, H. (1987). The Theory of Recursive Functions and Effective Computability. First MIT press paperback edition. ISBN 0-262-68052-1.
• Soare, R. (1987). Recursively enumerable sets and degrees. Springer-Verlag. ISBN 3-540-15299-7.

• Weisstein, Eric W., Kleene's s-m-n Theorem at MathWorld.