# Problems understanding proof of s-m-n Theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem:

Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a computable function $g(x)$ such that $f(x,y) = \Phi_{g(x)}(y)$ for all $x,y \in \mathbb{N}$. Here, $\Phi_n$ refers to the $n$th recursive function.

The proof goes like this:

For a fixed $x_0$, the function $h_{x_0}(y) = f(x_0,y)$ is computable (this I agree with) and so there exists an index $e_{x_0}$ so that $h_{x_0} = \Phi_{e_{x_0}}$ (this I also agree with).

So, the function $g$ that to each natural $x$ assigns such index $e_x$ (so that $h_x = \Phi_{g(x)}$) is computable (this is the part I don't understand).

When saying that $g$ is computable it means that we can describe an algorithm that takes $x$ as an input and will output the desired $g(x)$. I don't see how such algorithm can be described. (I guess my confusion has to do with the "there exists an" that I placed in bold letters.)

If it helps, we are using Godel numberings of Turing Machines to index the recursive functions.

I guess it should be $h_{x_0}(y) = f(x_0, y)$. I'm assuming your Turing machines have unary inputs and use states $q_0, q_1, \dots$. I describe the general idea, and if you're allowed to appeal to Church-Turing thesis, then it should be convincing, otherwise you should write down the program for the Turing machine described below (it depends on $x$) and plug it into your specific Godel numbering function. In the latter case you will obtain $g(x)$ explicitly and see that it is not only computable but also primitive-recursive (provided that your numbering is).

Roughly speaking $\Phi_{g(x)}(y)$ does the following: it prints $x$ on the tape before $y$ and runs the (slightly modified) program for $f(x, y)$ on these inputs. So we need to check that the program for this routine depends computably and uniformly on $x$. Let's go into some more details.

Let $P$ be a program that computes $f(x, y)$. We describe the program that computes $\Phi_{g(x)}(y)$. It has $y$ on the tape. At first it executes simple "insert $x$" program as follows. It moves head left by $x+1$ cells, writes $x$ and places head at the first digit of $x$. So now we have $x$ and $y$ on the tape. This can be done using (not more than) $2x$ states $q_0, q_1, \dots, q_{2x}$ (you can replace $2x$ with any computable function $h(x)$ that bounds the number of states needed to perform these actions). After that it executes $P'$ on these inputs, where $P'$ is obtained from $P$ by adding $2x + 1$ to all state indices (to ensure that its set of states doesn't intersect the set of states for the "inserting $x$" program).

Now $g(x)$ is the number of the Turing machine which does all the stuff described above. To convince yourself that $g$ is computable, you need to check that the program above depends on $x$ in a computable uniform way. Indeed, "inserting $x$" program is easy to write and calculate its number in terms of $x$. If you have a number of $P$, then the number of $P'$ is obtained from it in a computable way - $P'$ differs only in state indices and they are also changed using computable function $(i, x) \mapsto i + 2x + 1$. After that the number of the program obtained by concatenation of "insert $x$" program and $P'$ (given that they have non-intersecting sets of states) can be also easily computed. Thus, $g(x)$ is computable.

• This is amazing, thank you. Just to make sure I understood correctly, what makes $g$ computable is that, apart from $f$ being computable, you can build/describe the program that computes $\Phi_{g(x)}(y)$ computably? So the "inserting $x$" is easy to write in the sense that we can algorithmically (using Church-Turing thesis) describe how, with input $x$, we can write the "insert $x$" subroutine and add it at the beginning of the program that calculates $f$? – SantiagoC Mar 4 '16 at 4:53
• Yes, exactly. S-m-n theorem is roughly no more than just plugging in $x$ input while leaving $y$ free. The main point is that the resulting program computably and uniformly depends on $x$ (that's a more rigorous form of "you can build/describe the program computably") , and hence its number $g(x)$ is a computable function. – Random Jack Mar 4 '16 at 7:57
• Thank you @Random. What do you mean when you say that the resulting program depends "uniformly" on $x$? Do you have any other recommended bibliography on this matter? – SantiagoC Mar 5 '16 at 18:40
• Well, probably I misused this word here. I just wanted to say that its structure is the same for all values of $x$ (it performs one task that depends on $x$) and so its number is a computable function of $x$. The word "uniformly" is used in computability theory when some proof (or construction) depends computably on the input. For example, the class of recursive sets is closed under $\cup$ uniformly (meaning that you can find a computable function $f(x, y)$ with $W_{f(x, y)} = W_x \cup W_y$). – Random Jack Mar 5 '16 at 19:01
• However, the closure under complementation is not uniform (meaning that there is no computable function $f(x)$ with $W_{f(x)} = \overline{W_x}$). I would recommend the classics: Hartley Rogers, "Theory of Recursive Functions and Effective Computability". §5.5 introduces the notion of "uniformity". – Random Jack Mar 5 '16 at 19:05