"Tim Little" <tim@little-possums.net> wrote in message news:slrni1m1tk.jrj.tim@soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> There are a countable number of computable Reals. > > Correct. > >> You can apply the Cantor construction to any purported list of all >> computable Reals to form a computable Real not on the list. > > No, you can apply the Cantor construction to any purported list of all > computable Reals to form a *non*computable Real not on the list. >
Wrong. Cantor's diagonal construction explicitly forms a Real not on that list, and the Cantorm diagonal number is obviously constructibe if every item in the list is constructible. Cantor provides a very simple, explicit algorithm for constructing the diagonal number.
> >> This proves that the computable Reals cannot be listed. > > It proves no such thing.
Well, that is what Cantor's proof exactly shows. It shows that if there was a list of all Reals, we can produce a Real not on the list, so the Reals cannot be listable.
> > >> It does *not* prove the computable Reals are uncountable, and in >> fact they are not. > > Of course the computable reals are countable. I never claimed > otherwise. You are the one claiming that they cannot be listed, a > statement equivalent to their uncountability.
No, they are not the same.
If you believe that you have a list of all computable Reals, I can use a diagonal argument to explicitly construct a Real not on the list. This number is obviously computable; Cantor provides an explicit algorithm for constructing it, which can be implemented in a few lines of code or in a TM.
> > >> In exactly the same manner, Cantor proved that the Reals cannot be >> listed. This does *not* automatically mean they are uncountable, >> any more than the same proof applied to computable Reals proves they >> are uncountable. These are different concepts. (Although they were >> not when Cantor produced his proof). > > Computability as a concept did not even exist when Cantor produced his > proof.
Correct.
> You are extremely confused. >
No. You seem to think that the computable Reals can be listed. They can't. Given a list of computable numbers, we can compute (explicitly construct) the diagonal number, and prove its not on the list. But yet they are countable.
Cantor did not prove that the Reals are uncountable using his diagonal proof, and as far as I am aware he didn't claim that it did. Computable numbers can't be listed either, and they are countable. These are different concepts which you (incorrectly) seem to think are the same thing.
