"K_h" <KHolmes@SX729.com> wrote in message news:0radndv17q0_14HRnZ2dnUVZ_uydnZ2d@giganews.com... > > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1c3a11$0$18229$afc38c87@news.optusnet.com.au... >> >> "K_h" <KHolmes@SX729.com> wrote in message >> news:ALWdnQzHH6Fug4HRnZ2dnUVZ_gKdnZ2d@giganews.com... >>> >>> "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message >>> news:4c1b24ce$0$17177$afc38c87@news.optusnet.com.au... >>>> >>>> "Tim Little" <tim@little-possums.net> wrote in message >>>> news:slrni1m2q9.jrj.tim@soprano.little-possums.net... >>>>> On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> >>>>> wrote: >>>>>> "Tim Little" <tim@little-possums.net> wrote in message >>>>>>> Cantor's construction applied directly to lists of computable >>>>>>> numbers >>>>>>> shows almost nothing. Given any list of computable reals, you can >>>>>>> produce an antidiagonal real not on the list. Unfortunately the >>>>>>> construction says nothing about whether the antidiagonal is >>>>>>> computable >>>>>>> or not. >>>>>> >>>>>> Of course its computable. It is a trivial programming exercise to >>>>>> form a >>>>>> computable number not on the list, by simply doing digit >>>>>> substitutions. >>>>> >>>>> Only if the list itself is a computable function. Cantor's proof does >>>>> not depend on any such assumption. >>>>> >>>> >>>> If you give me a purported list of all computable numbers, I can >>>> explicitly >>> >>> QUESTION 1: >>> But ask yourself: is the list of all computable real numbers itself >>> computable? Each real in such a list is computable but can you find a >>> computable function that says which computable real is mapped to 0, >>> which computable real is mapped to 1, which computable real is mapped to >>> 2, and so on? >>> >> >> No. >> >>>> construct a Real not on the list. Of course this number is computable; >>>> there is a simple algorithm to compute it. >>> >>> But ask yourself: since the algorithm you use to compute it calls on the >>> "algorithm" I asked you about in QUESTION 1, is your algorithm depending >>> on another "algorithm" that is non-computable? >>> >> >> The algorithm does not exist. There can be no list of all computable >> Reals. > > No, there is no finite algorithm that can generate the list but that does > not mean that such lists don't exist. There are lists that contain all > computable reals.
So using this logic and applying it to Cantor's original proof, there may also be lists of all Reals, but there is no finite algorithm which can generate the list?
If this were the case, then the Reals would be countable.
How do you know that Cantor's proof that that there can be no list of all Reals is simply because there is no finite algorithm to produce the list, and not because they are uncountable?
> >>>> No. And in fact Cantor's diagonal proof does not prove the Reals are >>>> uncountable, just that they cannot be listed. Which is all he claimed. >>> >>> No, because Cantor's diagonal argument applies to lists that are not >>> computable as well as to lists that are computable. >> >> So Cantor's proof when applied to computable Reals proves exactly what in >> your opinion? > > If I understand your question, all it shows is that the anti-diagonal > number is not computable. >
Its easy to compute.
Cantor's proof requires a purported list of all Reals, such that the nth digit of the nth item can be determined. My proof requires exactly the same thing. The computation to derive the nth digit of the anti-diagonal is simple and explicityly constructs the anti-diagonal number. Its hard to argue this number cannot be computed when Cantor provides an explicit means of computing it.
>> So the computable Reals cannot be listed. >> Yet they are countable. >> So a proof that a set cannot be listed does not prove it is uncountable. > > The computable reals can be listed and so they are countable. >
Sweet. Give me such a list, and I will *compute* a number not on the list.
>>>> You give me that list. >>> >>> Yes, every real in the list is computable. But ask yourself: is the >>> function that maps each natural to each of these reals itself >>> computable? >> >> No. >> They cannot be listed. > > Yes they can but not by a finite algorithm. >
And exactly where does the bit about a "finite algorithm" appear in Cantor's original proof?
Cantor asks for a list of Reals - defined in advance - and then produces Real not on the list. The list he requires specifies each Real sufficiently to identify the nth decimal place of the nth item.
I ask for a list of computable Reals - defined in advance - and produce a computable Real not on the list. My requirements on the structure of the list are *identical* to those used by Cantor - the list must identify each item sufficiently to identify the nth decimal place of the nth item.
How is my proof different to Cantors?
And if my proof does not demonstrate that the computable numbers are uncountable, why do you think that the same proof applied to all Reals proves that they are uncountable?
