My feeling is the computable numbers are countable because they are associated with a finite string of symbols that give an algorithm for computing the number to arbitrary precision. The set of all finite strings in a given language is obviously countable as it is the countable union of finite sets.

Because $\mathbb R\setminus\textrm{Computable}=\textrm{Uncomputable}$, the uncomputables are uncountable.

  • 1
    $\begingroup$ That's an excellent way of thinking about it; what you've given is basically the core argument for countability of computable numbers. (But nitpickery: you need your 'given language' to have either a finite or countable number of sentences!) $\endgroup$ – Steven Stadnicki Dec 13 '17 at 9:14
  • $\begingroup$ Good point. Can I just say that a sentence in language must be finite (infinite sentences are either unrealizable by computation or are themselves defined by a finite algorithm), and if the symbols in language are from a finite set (which should be true), then the set of all sentences/algorithmic computations is S0 U S1 U S2 U... where Si = set of sentences “I” long. Countably infinite union of finite sets is countable, for obvious reasons. $\endgroup$ – Marcus Aurelius Dec 13 '17 at 9:29
  • $\begingroup$ Is it also true that this “language” is even simpler than the stuff you see in math textbooks, with sigmas and relations, etc...and actually only associates a Turing machine (where a given number of states determines a finite number of machines) and a start tape to a computable number? $\endgroup$ – Marcus Aurelius Dec 13 '17 at 9:32

Yes. That is the reason. Here is a more explicit explanation.

We are using two theorems here:

  1. If $A$ is countable, then the set of finite strings with characters in $A$ is countable.

  2. If $A$ is countable and $f\colon A\to B$ is a surjective function, then $B$ is [finite or] countable.

The first theorem tells us that indeed there are only countably many Turing machines—or whatever equivalent model of computation that you prefer to think about—and the second theorem tells us that since the map from a Turing machine to the real number it computes (assuming it computes one) is an obvious surjective function from the Turing machines onto the computable reals, there can be only countably many reals.

Of course, it still remains to verify that there are infinitely many computable reals, but that one is an easy exercise I will leave you.

And finally, since $\Bbb R$ is uncountable, if we remove a countable set of reals we keep an uncountable set of them. And in fact, the remainder has always cardinality $2^{\aleph_0}$. So indeed the set of uncomputable reals is uncountable.


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.