Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Matheology § 257
Posted:
Apr 22, 2013 3:03 AM


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 measuretheoretic 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 "uncountabilityproofs". 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 nonmeasurably small share of all usable finite programs has bee used.
Regards, WM



