Date: Apr 22, 2013 3:03 AM
Author: mueckenh@rz.fh-augsburg.de
Subject: Matheology § 257

Matheology § 257

The set of all possible computer programs is countable {{if going into
concrete details of computers, we can even say more restrictively: The
number of all possible programs is finite and certainly less than
2^10^100. But of course Turing did not refer to real computers and did
not know anything about the memory space of an exploitable
surronding. Therefore let us analyze his approach here.}}, therefore
the set of all computable reals is countable, and diagonalizing over
the computable reals immediately yields an uncomputable real. Q.E.D.
{{Well, it is not always that easy to diagonalize over finite
sequences. The following list has no diagonal:
0
1
So we must take some more care, as will be done in the following.}}
Let's do it again more carefully.
Make a list of all possible computer programs. Order the programs
by their size, and within those of the same size, order them
alphabetically. The easiest thing to do is to include all the possible
character strings that can be formed from the finite alphabet of the
programming language, even though most of these will be syntactically
invalid programs.
Here's how we define the uncomputable diagonal number 0 < r < 1.
Consider the kth program in our list. If it is syntactically invalid,
or if the kth program never outputs a kth digit, or if the kth digit
output by the kth program isn't a 3, pick 3 as the kth digit of r.
Otherwise, if the kth digit output by the kth program is a 3, pick 4
as the kth digit of r.
This r cannot be computable, because its kth digit is different
from the kth digit of the real number that is computed by the kth
program, if there is one. Therefore there are uncomputable reals, real
numbers that cannot be calculated digit by digit by any computer
program. [...]
In other words, the probability of a real's being computable is
zero, and the probability that it's uncomputable is one. [Who should
be credited for this measure-theoretic proof that there are
uncomputable reals? I have no idea. It seems to have always been part
of my mental baggage.]

[Gregory Chaitin: "How real are real numbers?" (2004)]
http://arxiv.org/abs/math.HO/0411418

The error occurs always at the same plase - that is common to all
"uncountability-proofs". The completed infinite number of all finite
programs is presupposed. Otherwise the just defined number would be
generated by another finite process with a finite program. But the set
of all finite things is not a completed infinity, it is potentially
infinite. After all you cannot use a program that is longer than the
longest program that is used. Nevertheless, up to every length, only a
non-measurably small share of all usable finite programs has bee used.

Regards, WM