"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.
>>> 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.
> 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.
>>> 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.
