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


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

  • $\begingroup$ 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. $\endgroup$ Jul 14 '16 at 6:59
  • $\begingroup$ That is not helpful. Where does it lack precision? $\endgroup$ Jul 14 '16 at 12:49
  • $\begingroup$ 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. $\endgroup$ Jul 14 '16 at 13:08

I think you are reading it backwards.

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.

  • $\begingroup$ 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. $\endgroup$ Jul 14 '16 at 12:55
  • $\begingroup$ 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. $\endgroup$
    – chi
    Jul 14 '16 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.