3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – SantiagoC Mar 4 '16 at 4:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Random Jack Mar 4 '16 at 7:57
  • $\begingroup$ 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? $\endgroup$ – SantiagoC Mar 5 '16 at 18:40
  • $\begingroup$ 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$). $\endgroup$ – Random Jack Mar 5 '16 at 19:01
  • $\begingroup$ 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". $\endgroup$ – Random Jack Mar 5 '16 at 19:05

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.