Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.