Problems understanding proof of smn theorem using Church-Turing thesis

Question

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,y)$ is computable (this I agree with) and so we 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.

Answer 1

In books on computability theory it is common for the text to skip details on how a particular machine is to be constructed. The author of the computability book will mumble something about the Turing-Church thesis somewhere in the beginning. This is to be read as "you will have to do the missing parts yourself, or equip yourself with the same sense of inner feeling about computation as I did". Often the author will give you hints on how to construct a machine, and call them "pseudo-code", "effective procedure", "idea", or some such. The Church-Turing thesis is the social convention that such descriptions of machines suffice. (Of course, the social convention is not arbitrary but rather based on many years of experience on what is and is not computable.)

I am not saying that this is a bad idea, I am just telling you honestly what is going on. Books on analysis skip $\epsilon\delta$-proofs, books on category theory don't verify every naturality square, books on topology rely on geometric intuitions of the readers, etc.

There are standard tricks on how to read computability theory. If the book says "there exists $X$", then that usually means "$X$ can be computed from whatever our current parameters are". If they want to emphasize that whatever they are doing can be computed as a function of a parameter $p$, they will say "whatever we are doing, uniformly in $p$". And obviously, if they say "non-uniformly in $p$", they are emphasizing that whatever they are doing is not computable as a function of $p$.

In Barry's text, he could have emphasized the computability bit by writing "there exists an index $e_{x_0}$, uniformly in $x_0$, such that ..." But since this is an introductory text, sticking in the word "uniformly" will just confuse a good part of the readership. So what are we supposed to do? We certainly do not want to write out detailed constructions of machines, because then students will end up thinking that's what computability theory is about. It isn't. Computability theory is about contemplating what machines we could construct if we wanted to, but we don't. As usual, the best path to wisdom is to pass through a phase of confusion.

Answer 2

So $g$ is a function such that $\Phi_{g(x)}(y)=f(x,y)$.

All this means is that $g$ on input $x$ will output (print on its tape, if you will) a program $P$ that does the following:

Code for $g(x)$:

1. $P$ has the information about $x$ hard-wired, either on a separate tape or in its state control.
2. $P$ reads its input $y$.
3. $P$ then turns $x$ and $y$ over to a program $Q$ for $f$ and runs $Q$.

By Church's Thesis, this $g$ is computable, basically because I just described in pseudocode how to print the program code $g(x)$ above, in items (1)-(3).

Answer 3

To provide intuition, I think it helps to think about the code underlying these functions, pretending it is written in a familiar language or pseudocode.

Assume $f(x,y)$ is implemented in some way as

fun (x,y): some_code; return something

Then, $g(x)$ is the following

fun (x): return "fun(y): x = " + str(x) + "; some_code; return something"

which, on any specific constant $a$, produces the output string

fun (y): x=a; some_code; return something

essentially "hard-coding" the vale $a$ for the first parameter $x$ in the code implementing $f$.

Then, $\Phi_{g(a)}(b)$ simply evaluates the string $g(a)$ and applies the resulting function to input $b$.

Answer 4

A fundamental problem with the use of the s-m-n theorem is that often it is assumed that it somehow yields indexes, while in fact it is just using indexes.

Of course, indexes require for their computation an encode/decode pair of functions, and for indexes of the enumeration type these functions use an infinite number of steps.