# smn-theorem: Application by instantiating s<m, n> with other function

The smn-Theorem on the basis of Turing Machines and computable functions rather than programs, as in the Wikipedia article for instance, can be defined as follows:

\begin{align*} &&& s \langle m, n \rangle &&= \lceil M' \rceil \\ &&\implies &\varphi_{s\langle m, n \rangle} &&= \varphi_{\lceil M' \rceil}\\ &&&&&= f_{M'}\\ &&\implies &\varphi_{s\langle m, n \rangle} (i) &&= f_{M'}(i)\\ &&&&& = f_{M_m} \circ f_{M_{\langle n, . \rangle} (i)}\\ &&&&&=\varphi_m \langle n, i\rangle \end{align*}

where $M_{\langle n, . \rangle}$ denotes, that machine $M_{\langle \rangle}$ has $n$ already pre-written on its tape and $\lceil M \rceil$ denotes the Gödel-number of machine $M$.

Now, I am confronted with the claim, that

$$\varphi_{h(n)}(i) = f\langle n, i \rangle$$

because

$$f := \varphi_m \in \text{set of computable functions}$$ then $$f\langle n, i \rangle = \varphi_m \langle n, i \rangle = \varphi_{s \langle m, n \rangle}(i)$$

therefore it has to be that

$$h(n) = s\langle m, n \rangle$$

so I guess then it has to be like this: $$h(n) = \lceil M' \rceil = \lceil f_{M_m} \circ f_{M_{\langle n, . \rangle }} \rceil = s\langle m, n \rangle$$

And so $h$ contains $f_{M_m}$ ... basically just because there can be such a function? Am I interpreting this right?

• A theorem is stated, claimed or formulated, but it is not "defined". Also, your statement of the smn theorem lacks precision, and therefore you open yourself up for misinterpretation. – Andrej Bauer Jul 14 '16 at 6:59
• That is not helpful. Where does it lack precision? – lo tolmencre Jul 14 '16 at 12:49
• Because it lets the reader guess what the assumptions and the conclusions of the theorem are. You are in fact showing what looks like a chunk of the proof of the theorem, not the theorem itself. And I am not so much complaining for myself as I am for you. If you state the theorem clearly, chances are you will see what's going on better. – Andrej Bauer Jul 14 '16 at 13:08

Usually you want to find $h$ such that $\varphi_{h(n)}(i) = f(n,i)$, where $f$ is a computable partial function. Further, you want $h$ to be total recursive (or even more: primitive recursive).
In order to prove that such an $h$ exists, as well as to concretely define it, one picks any index $m$ for $f$, so that $\varphi_m = f$, and chooses $h(n) = s(m,n)$.
Note that, when reading the reasoning above in the other direction, it becomes wrong. That is: it is not the case that, since $\varphi_{h(n)}(i) = f(n,i)$ we can conclude $h(n) = s(m,n)$.
Indeed, $h$ may also be another function, like e.g. $h(n) = pad(s(m,n))$ where $pad$ is a padding function (which returns the Gödel number for an equivalent TM, such that said Gödel number is larger). Infinitely other (computable) $h$ exist.
• How can we choose $h(n) = s\langle m, n \rangle$ if we can not conclude that $h(n) = s\langle m, n \rangle$ based on $\varphi_{h(n)}(i) = f(n, i)$ if we can say that $f = \varphi_m$? Can you rephrase that, because this way I don't understand what you mean. – lo tolmencre Jul 14 '16 at 12:55
• As I wrote, such $h$ is just one of infinitely many solutions. Consider the problem of finding some $x$ such that $x^2 > x$. I can choose $x=5$ and be OK with that, even if this is not the only solution. Indeed, we are not claiming this is the only possible choice -- just one that satisfies the requirements. – chi Jul 14 '16 at 13:08