Cheap and Secure Web Hosting Provider : See Now

[Answers] Why does my answer sheet say the set of computable functions is uncountable?

, , No Comments
Problem Detail: 

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.

Asked By : estebarb

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback