# Why can't we diagonalize out, if we deal with partial functions?

We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try to apply a "diagonal" argument to them: Let $g(n)=f_n(n)+1$, if $f_i$ is the $i$-th (partial) recursive function. Now, $g$ can't be (partially) recursive, because otherwise it would be one of the $f_i$'s, so we would get a contradiction. But my instructor mentioned in class, that we don't get a contradiction, if we restrict ourselves just to partial recursive functions. I am not sure if I understood him correctly, but could maybe someone here enlighten me, whether it makes sense what he said ? Because it seems to me that this assertion is wrong... Or, if I misunderstood, in which context it would make sense what he said ?

-

This argument breaks for partial recursive functions since if $f_n(n)$ doesn't halt then $g(n) = f_n(n) = \bot$.

-
Could you please explain, what the symbol on the LHS means ? Undefined? – temo Apr 30 '11 at 21:26
$\bot$ here means the program doesn't halt. – Yuval Filmus Apr 30 '11 at 22:03
But if $g$ is for example $f_k$ and $f_k (k)$ wouldn't halt, than I would still my contradiction! So how can I be sure, that none of the $f_n (n)$ halt ( - which is what I need if I don't want contradiction occuring) ? – temo May 1 '11 at 16:35
And what would happen if we define $g(n)$ as $f_n (n)$ if $f_n (n)$ halts and as $0$ otherwise ? – temo May 1 '11 at 16:37
@temo: since the halting problem is not decidable, if you define $g(n)$ like that there is no reason to think it is computable. – Carl Mummert May 1 '11 at 17:37

Consider also this, first paragraph, page 39 - although I don't now if that is clear enough for you; I have the feeling you want a more detailed explanation, but now I don't have the time to provide one.

-

$g$ can be any of the $f_i$ such that $f_i(i)$ is not defined or does not halt. In particular, you only need one of those to exist.

In fact, it turns out $g$ is computable. Consider this: your favourite programming language gives rise to a surjective map from the set of finite strings of characters (i.e. source files) to the set of computable functions (i.e. programs) – this map is the compiler or interpreter of your language. But it's easy to write a function which enumerates all possible finite strings, so just compose that with a compiler and you get a function which enumerates all possible computable functions.

So applying a diagonal argument to partial computable functions is surely bound to fail.

-