I have a question on the statement of the s-m-n Theorem and the implication $$ \varphi_{f(x,y)} = \lambda z \varphi_x(\varphi_y(z)) $$ for some recursive function $f(x,y)$ cited in the above link. In what sense does this follows from the s-m-n theorem and in what sense does it gives anything new?

To be more specific. As I see it to apply the s-n-m-theorem the function on the right side must be partial recursive or computable, but $\varphi_x(\varphi_y(z))$ is just the composition of computable functions (by the universal turing machine theorem $(y,z) \mapsto \varphi_y(z)$ and so on are computable). But knowing this already says that it has some Gödel coding, and the fact that this is effective (and total) is given by the typical proofs that the composition of computable functions is computable (i.e. by giving an algorithm to construct a suitable Turing machine). So the statement that there exists some recursive $f(x,y)$ gives nothing new to what I know from the basic proof that the composition of computable functions is computable?

So have I missed anything? Or in what sense does this follow from the snm-theorem? And does it states anything nontrivial?


1 Answer 1


Your assumptions on composition are quite strong. The idea, here, is that you are only assuming that the class of (partial) computable functions is closed with respect to composition (so you only know that you must have some program computing it) and then use smn to prove that you can uniformely and effectively compute an index for such a program from the indexes of the programs you are composing (x and y in your example).

Instead of spending time to show that you can effectively construct a turing machine computing the composition of two other turing machines (that is not so trivial) it is better to spend some time to prove smn, that gives you a much more general technique:

  1. it proves that any partial instantiation of a computable function is still computable
  2. it tells you that you may compute the index of the partial instatiation in a uniform and effective way in terms of the index of the source program and the parameters of the given instantiation (hence, providing a form of parameter abstraction, quite similar to lambda abstraction).

Coming back to your examples, the "source" function is

$$g(x,y,z) = \varphi_x(\varphi_y(z))$$

and you are computing the partial instantiation of $g$ with respect to x and y. The point is that $g$ can be any computable function, and you are free to choose your parameteres in any way you like. A real jolly.

I strongly suggest you to have a look at the following answer on mathoverflow, that gives a very, very nice explanation of smn.

  • $\begingroup$ Thanks. Guess I also identified partially recursive with computable by Turing machine, but as written here en.wikipedia.org/wiki/%CE%9C-recursive_function if we use this definition without Turing machiens, then they are closed under composition by definition. But this does not tell us how the (Gödel) numbers/indices of these functions you get by composition are related. $\endgroup$
    – StefanH
    Commented Mar 7, 2017 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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