Non computable real numbers

Question

A real number $r$ belonging to $[0,1]$ is said to be computable if there is a simple TM such that for each binary encoding of $n$ ($n$ is a natural number), returns the $n$th bit in the binary expansion of $r$. Give a proof that there are non-computable real numbers.

Answer 1

By a cardinal argument :

1. You have $2^{\aleph_0}$ reals in $[0;1]$
2. You have $\aleph_0$ Turing machines.
3. There is no bijection between $\aleph_0$ and $2^{\aleph_0}$

Answer 2

It's a diagonal argument. You have to assume (or read it somewhere) that there are strictly more real numbers than natural numbers. It is a theorem, and it can be proved in several ways, but it's not the point here. The point is that you have to know that any function from $\mathbb{N}$ to $\mathbb{R}$ (or any interval thereof) leaves most point out of the image.

The easiest way to do this is to use the famous Cantor diagonal construction, where you supposedly have an enumeration $e:\mathbb{N}\to\mathbb{R}$ of all the real numbers, and you prove that there is at least one real number not in it, by "writing them down" in an infinite matrix, and taking a number that is different from the diagonal of the matrix at each decimal place.

On the other side, you have Turing Machines. They are in a natural correspondence with $\mathbb{N}$, so different TMs map to different numbers (but not all natural numbers correspond to TMs). Some of these turing machines will actually be machines that compute a computable real number (not all of them do, but it doesn't matter). So you have a set $Comp\subseteq\mathbb{N}$ of number that represent TMs which compute computable real numbers. If there were no noncomputable real numbers, then this correspondence would be an enumeration of the reals, and we saw befaore that there is no such enumeration. $\QED$