"Tim Little" <tim@little-possums.net> wrote in message news:slrni1r04q.jrj.tim@soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim@little-possums.net> wrote in message >>> That is only a "finite, terminating algorithm" if the list is finite. >>> Since the only input to the algorithm is the desired precision, your >>> recipe only works if you can embed the list into the algorithm. >> >> No. You could level the same argument against Cantor's original proof. > > No you couldn't, as it makes no assumption of any finite algorithm. > Only *your* alteration of Cantor's proof assumes any sort of finite > algorithm, as it is required for the definition of "computable real". >
I don't say anything about finite algorithms. I just ask for a list of computable Reals, in the same form a Cantor asks for a list of Reals.
> >> For a number to be computable, it must be able to be calculated to >> any required degree of accuracy (according to the definition we have >> just both agreed on). This is obviously true of the anti-diagonal. > > Only if the list is computable, which Cantor's proof does not require. >
Exactly how are my requirements for the list different from Cantor's, excepting that my list contains computable Reals and his requires any Real?
> >> Cantor provides an explicit algorithm for constructing (computing) >> the anti-diagonal. > > No, the proof only provides an algorithm fragment. A full algorithm > for a computable real must take the precision as input, and nothing > else. The constructive portion of Cantor's proof takes an infinite > list of real numbers as "input", and so is not a valid algorithm for a > computable real. >
No, if you want to use this definition of a computable Real (slightly different to the one we have been using, but equivalent), to determine the anti-diagonal to n places only requires the first n items on the list be examined, and hence is finite.
> >>> If not, how does this differ from "suppose L is a list of real >>> numbers. Is antidiag(L) computable?" >> >> Because there is an algorithmic procedure for calculating the >> anti-diagonal to any required degree of accuracy. > > If you are given L, you say you can compute antidiag(L) regardless of > what L is.
Yep. Easy. The nth digit of L is "1" if the nthe digit of the nth term is "2", otherwise it is "1".
As I can easily specify every digit in its decimal expansion, it is of course computable.
> If you are given x, can you not compute x+1 regardless of > what x is? By your argument, does this not mean that x+1 is always a > computable real? >
As long as x is computable.
And the input list by definition only contains computable Reals.
> > - Tim
You remind me of one of those anti-Cantor cranks who keep trying to find a flaw in Cantor's proof. My proof and his are virtually identical. Cantor proved the set of Reals is not recursively enumerable, and my proof shows the set of computable Reals is not recursively enumerable. This is not quite the same thing as being uncountable.
