"Tim Little" <tim@little-possums.net> wrote in message news:slrni1r0ra.jrj.tim@soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> Explain to me how my requirements for the input list of all >> computable Reals is different to Cantor's requirements for the input >> list of all Reals, other than the requirement that every item on the >> list is computable? > > It is not. Your error comes later. > > Cantor's proof includes a construction taking a list L and defining an > antidiagonal real antidiag(L) from it. Your error is supposing that > this construction is a finite algorithm fitting the definition of > "computable real". It is not. By stretching the definition of > "algorithm" somewhat, it can be supposed to be an algorithm accepting > finite input n and infinite input L, and producing the n'th > antidiagonal digit. This is a stretch since algorithms are normally > not supposed to have infinite inputs.
The calculation of the nth digit only requires the first n digits to n decimal places, and hence it is clearly a finite algorithm.
Its simply ludicrous to suggest that the antidiagonal is not computable given that a very simple algorithm will explicitly churn it out.
> > However, there is no way that you can then prove the existence of a > finite algorithm accepting only the *finite* input n and producing the > n'th antidiagonal digit. >
Of course I can prove the existence of a finite algorithm. I can produce it.
To produce the nth decimal of the anti-diagonal, look at the first n items on the purported list of all computable Reals. Then substitute "1" for "2" blah blah. How is that not a finite algorithm? I can produce the nth decimal place of the anti-diagonal purely by counting down to the nth Real on the list and looking at the nth digit. I can code it in Java in 3 lines. Exactly as per Cantor's proof.
> >> (in more modern terminology) that there is no recursively enumerable >> mapping > > Once again, "recursively enumerable" is an introduction purely of your > own invention.
As I said when I introduced it. It does not appear in Cantor's proof or mine. It is an explanation of why this somewhat paradoxical result applies, that Cantor's form of proof applied to computable Reals also produces the conclusion that any such list cannot be complete. Not that it is much of an explanation; not being recursively enumerable means pretty much the same thing as having no explicit mapping from N.
As somebody else pointed out, computable Reals are enumerable but not recursively enumerable.
Cantor's form of proof applied to computable Reals shows only that they are not recursively enumerable, not the stronger condition that they are uncountable. Similarly, Cantor's proof really only shows that the Reals are not recursively enumerable, not that they are also denumarable (uncountable).
> It is not present in Cantor's proof, it is not present > in a modern recasting of Cantor's proof, it has no relevance at all to > Cantor's proof.
Well, I think I am making a pretty good hand of my case. But yes, I know what I am saying is not accepted. I am genuinely confused by this - the fact that my opinions are unique, and I would expect therefore to be almost certainly wrong (with probability 1). On the other hand my argument seems pretty solid to me.
> Cantor's proof applies to *every* mapping from N to R. >
Ummm ... mine applies to every mapping from N to computable Reals.
> > - Tim
Really, if you have some list of computable Reals to give me, I would be happy to provide the anti-diagonal. And lets remember what a "computable Real" is, it is a Real which can be specified to any arbitrary degree of accuracy. As a practical matter, you don't have to list every one in full; I only require the first n digits.
