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



Re: Matheology § 257
Posted:
Apr 23, 2013 10:37 AM


On Apr 22, 3:03 am, WM <mueck...@rz.fhaugsburg.de> wrote: > 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
BTW Turing handled the problem of finite memory by assuming you invest a lump sum of money in a profitable business that supplies paper as dividends at a faster rate than your computer uses it up!
CB



