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.  
 A: 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.
