Talk:Smn theorem

Title

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

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

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

• "smn theorem" at Mathworld

--- 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?

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)

Statement of basic form of theorem is confusing

Quote from the article:

Given a Gödel numbering $\varphi$ 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 partial computable function f with two arguments, the expressions $\varphi _{s(p,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers x and y, and their values are equal for any such combination.

I would rephrase it as follows

Given a Gödel numbering $\varphi$ of partial recursive functions, there is a primitive recursive function s of two arguments with the following property: for every Gödel number p of a partial computable (recursive ??) function with two arguments, the expressions $\varphi _{s(p,x)}(y)$ and $\varphi _{p}(x,y)$ are defined for the same combinations of natural numbers x and y, and their values are equal for any such combination.

(The statement of the more general form of the theorem seems clear to me as it is in the article.) My rationale for this proposed change is that, given the Gödel number of the function f, we can simply express it in terms of its Gödel number without cluttering the reader's mind with an extra variable name. Also the article should standardize terminology, viz. "partial recursive function" vs. "partial computable function". However, I do not want to make these change on my own since I am not an expert in this area. 71.222.14.246 (talk) 00:10, 22 March 2015 (UTC)

Smn or Snm?

Why is this named the "Smn theorem", rather than the "Snm theorem"? Typically the subscript is read before the superscript. — Preceding unsigned comment added by 205.204.46.103 (talk) 15:31, 9 December 2020 (UTC)