Sign up ×

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 ?

share|cite|improve this question

3 Answers 3

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

share|cite|improve this answer
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.

share|cite|improve this answer

$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.

share|cite|improve this answer

Your Answer


