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

Matheology § 257The set of all possible computer programs is countable {{if going intoconcrete details of computers, we can even say more restrictively: Thenumber of all possible programs is finite and certainly less than2^10^100. But of course Turing did not refer to real computers and didnot know anything about the memory space of  an exploitablesurronding. Therefore let us analyze his approach here.}}, thereforethe set of all computable reals is countable, and diagonalizing overthe computable reals immediately yields an uncomputable real. Q.E.D.{{Well, it is not always that easy to diagonalize over finitesequences. The following list has no diagonal:01So 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 programsby their size, and within those of the same size, order themalphabetically. The easiest thing to do is to include all the possiblecharacter strings that can be formed from the finite alphabet of theprogramming language, even though most of these will be syntacticallyinvalid 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 digitoutput 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 4as the kth digit of r.   This r cannot be computable, because its kth digit is differentfrom the kth digit of the real number that is computed by the kthprogram, if there is one. Therefore there are uncomputable reals, realnumbers that cannot be calculated digit by digit by any computerprogram. [...]   In other words, the probability of a real's being computable iszero, and the probability that it's uncomputable is one. [Who shouldbe credited for this measure-theoretic proof that there areuncomputable reals? I have no idea. It seems to have always been partof my mental baggage.][Gregory Chaitin: "How real are real numbers?" (2004)]http://arxiv.org/abs/math.HO/0411418The error occurs always at the same plase - that is common to all"uncountability-proofs". The completed infinite number of all finiteprograms is presupposed. Otherwise the just defined number would begenerated by another finite process with a finite program. But the setof all finite things is not a completed infinity, it is potentiallyinfinite. After all you cannot use a program that is longer than thelongest program that is used. Nevertheless, up to every length, only anon-measurably small share of all usable finite programs has bee used.Regards, WM
```