1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pål GD Apr 13 '15 at 3:07
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 13 '15 at 6:58
  • $\begingroup$ 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.) $\endgroup$ – Raphael♦ Apr 13 '15 at 10:13
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So, in the Hotel context: they have room for the "computable functions set", but not for the "all functions set", because the last includes non computable functions, that are not countable? $\endgroup$ – estebarb Apr 13 '15 at 4:15
  • 1
    $\begingroup$ Right. There are many more functions than computable functions. $\endgroup$ – Yuval Filmus Apr 13 '15 at 4:16
  • $\begingroup$ Ehm, sorry for the downvote ... Don't know how that happened. Just read the answer now, and saw I had a blue down-arrow on this answer. It says I downvoted it more than four hours ago and that the vote is locked unless the post is edited ... I have seriously no idea how that happened! $\endgroup$ – Pål GD Apr 13 '15 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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