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