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 ?
Why can't we diagonalize out, if we deal with partial functions?
3 Answers
This argument breaks for partial recursive functions since if $f_n(n)$ doesn't halt then $g(n) = f_n(n) = \bot$.
-
0@temo: since the halting problem is not decidable, if you define $g(n)$ like that there is no reason to think it is computable. – 2011-05-01
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.