0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What if we said no? (This sounds like your assignment, so you need to show some ideas.) $\endgroup$ – Ryan Reich Dec 6 '13 at 20:37
6
$\begingroup$

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}$
$\endgroup$
  • $\begingroup$ Can you give a proof that is a little more detailed and a little less technical. $\endgroup$ – user113939 Dec 6 '13 at 19:11
  • 1
    $\begingroup$ @user113939 If (s)he said any more (s)he'd have written the whole proof. $\endgroup$ – Ryan Reich Dec 6 '13 at 20:38
  • $\begingroup$ @user113939 To put it differently you can not pair off turing machines with real numbers because you have more reals than turing machines so there are reals that do not have any turing machine assigned to them. $\endgroup$ – Trismegistos Dec 10 '13 at 9:02
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Either is it a diagonal argument, or you have to assume that the real numbers outnumber the natural ones (the proof of which hides a diagonal argumnet). Not both. $\endgroup$ – Marc van Leeuwen Dec 6 '13 at 20:16
  • $\begingroup$ @Marc: Not really relevant, but there are proofs of the uncountability of $\mathbb R$ that don't depend on diagonals (such as Cantor's original proof which constructed a nested sequence of closed intervals). $\endgroup$ – Henning Makholm Dec 23 '13 at 15:32

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.