"Tim Little" <tim@little-possums.net> wrote in message news:slrni1teqk.jrj.tim@soprano.little-possums.net... > On 2010-06-21, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in >> message >>> Not so - the "very simple algorithm" you are suggesting requires >>> "the input list" in its raw (infinite) form as input. >> >> No. Computing the the anti-diagonall to n places only requires the >> first n items on the list to n digits of accuracy. > > Read the definition of computable real carefully, please! > > You need to show that there exists a finite algorithm that accepts > input n, with *no* additional input, and produces the n'th digit. >
Yes. Cantor produced such an algorithm. It is finite; the number can be specified to any arbitrary degree of accuracy in a finite number of steps with only a finite input.
Hell, I can do it by hand, so it must be finite. Give me your list of all computable Reals and I will compute the anti-diagonal to arbitrary precision for you.
> You don't get to put an upper bound on n when exhibiting the > algorithm. The same algorithm must work for all n. >
The same algorithm does work for all n. Look at the first n terms to n places of accuracy.
> For some fixed M, you could embed M digits of the diagonal into the > algorithm, and the algorithm would work for all n < M. But that's not > enough: it has to work for all n. >
I can in fact compute the nth digit of the anti-diagonal for any n by hand.
Cantor's original proof has the same requirements as mine. He asks for a purported list of all Reals and shows how to construct a missing Real. So do I. Of course I need to see the list first, and use this infirnite list in my proof, or else I couldn't tell you which Real is missing. But so does Cantor ...
> >> How is this number any less computable than the square root of 2? > > There exists a straightforward algorithm (e.g. Newton's method) to > calculate square roots to arbitrary precision. You can embed the > value 2 into an algorithm which accepts n as input, and applies > Newton's method to generate the first n digits of sqrt(2).
Given a purported list of all computable Reals, I can explicitly construct a Real not on the list to any required degree of accuracy.
> > You cannot embed the list L into an algorithm which applies the > antidiagonal procedure for arbitrary input n, as the list L is > infinite. You can only embed finitely many digits of L, and so there > will be an upper bound on the values of n for which the algorithm > works.
The same objection could be raised to Cantor's proof; after all, he accepts a purportedly infinite list as input to his algorithn as well.
> > >> I don't use the whole list. To calculate the nth digit of the >> anti-diagonal I only need the first n terms to n decimal places >> accuracy. That is a finite amount of data. > > However, you then need infinitely many different algorithms for > increasing n. A number is only computable if the same algorithm works > for all n. >
Well, the infinite list must be supplied in advance. Or else I can't work out what is missing. But then, Cantor's original proof has exactly the same rtequirement.
> >>> Now IF you could codify all this data somehow into a finite >>> program, so you had a computable function D(m,n) which produced the >>> n'th digit of the m'th number in the list, you would be OK. But >>> you DON'T have such a computable function D. >> >> Well, Cantor asks for a list of Reals. And D(m,n) is computable in >> my case by definition > > No, it is not. The m'th entry is computable for each m, with a > different algorithm for every m. For D to be computable, there must > exist a *single* finite algorithm that subsumes them all. There > exists no such algorithm. >
Well, the algorithm is clearly computable. If you give me a purported list of all computable numbers, I can compute a missing number.
Or are you saying I have to do this without using the infinite list itself? I note that Cantor's original proof also requires an infinite list of Reals, but you seem to have no problem with that.
