# Why does my answer sheet say the set of computable functions is uncountable?

I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox.

I was thinking that, because Gödel numbering, I could consider the set of computable functions as numerable (and with cardinality equal to $\mathrm{card}(\mathbb N)$). However, I have an answer sheet that says otherwise, and makes a proof of that I'm pretty sure that is wrong. At least I don't trust it:

Suppose that the computable functions set is enumerable, and $f_n$ is a function of the set. Consider $g(n)=f_n(n)+1$, its not in the set, therefore contradiction. Because that proof then the computable functions aren't countable, so they can't fit in the Hilbert Hotel.

• Is $g$ computable? If you want to show that there is a countable number of computable functions, you simply show that there is a countable number of Turing machines; Each Turing machine can be described by a finite string. The set of finite strings is countable. Are you mixing enumerable and countable? – Pål GD Apr 13 '15 at 3:07
• The answer sheet you quote seems to be confusing two similar-looking words. "Enumerable" means semi-recursive (i.e., there is a Turing machine that lists all the elements of the set); "DEnumerable" means countable (i.e., has the same cardinality as $\mathbb{N}$. The answer sheet proves that the set of computable functions isn't enumerable but that doesn't mean it's not denumerable. – David Richerby Apr 13 '15 at 6:58
• Please cite the original problem; this may well be a misunderstanding. Every set of computable functions is countable (because the set of all is) but not all are recursively enumerable, e.g. the set of total functions. (Well, given the phrasing you cite, the author of the answer sheet may just not know their stuff.) – Raphael Apr 13 '15 at 10:13

There are countably many computable functions. If $f_n$ is a complete list of all (total) computable functions, then the function $g(n) = f_n(n)+1$ cannot be any of the functions on the list, and so is not computable. This is one way to construct an uncomputable function.