Talk:Smn theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Foundations, logic, and set theory

Could the Title not be writen as s_{n}^{m} ?

I don't think so - due to technical restrictions sub- and superscripts are not presently possible. --Kizor 12:07, 24 November 2005 (UTC)

merged version by Math MArtin[edit]

In computability theory the smn theorem, Kleene's s-m-n Theorem or translation lemma is a basic result about computable functions first given by Stephen Cole Kleene.

smn theorem[edit]

Given a Gödel numbering

\phi:\mathbb{N} \to \mathbf{P}^{(1)}

of the computable functions with one parameter then for every computable function f with two parameters f \in \mathbf{P}^{(2)} there exists a total computable function \phi(i) \in \mathbf{R}^{(1)} so that

f(i,x) = \phi(r(i))(x) \quad i,n \in \mathbb{N}

External links[edit]

--- This was merged to S-m-n in Aug 2005, the result was brought back here so that the subscripts will work. Rich Farmbrough, 15:41 14 December 2006 (GMT).

Superflous sentences?[edit]

The following sentences from the scetion "Details" strike me as superfluous.

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.

In fact, the remainder of the section does not use any encoding scheme for numbers, just the usual Gödel numbering of computable functions.

Another remark: the section "Example" isn't an example at all. LISP is not a language of functions from (tuples of) natural numbers to natural numbers, and certainly not a language of primitive recursive functions. While it can operate on values representing LISP source code, this is not an example of Gödel numbering at all. I think the trivial implementation given is more misleading than illustrative, since the actual proof if the theorem (essentially the construction of the requested primitive recursive function) is far more complicated than the example suggests. Marc van Leeuwen (talk) 13:14, 1 March 2012 (UTC)