"Tim Little" <email@example.com> wrote in message news:firstname.lastname@example.org... > On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> I can use the Cantor diagonal construction to create a Real not on >> the list, which means that it is not a computable number. > > ... fine so far... > >> So the list cannot contain all computable numbers. > > Another WTF-worthy statement. All that shows is that if all > computable reals can be listed (which they can), there exists at least > one uncomputable real (which isn't on that list). > > > - Tim
If you can construct a list of all computable numbers (which you can't), then Cantor's diagonal proof will construct a number not on the list. And that number is definitely computable, because there is a simple algorithm for producing it. Take the nth digit of the nth item on the list and if it is a "1" change it to a "2" and if it is anything else change it to a "1". About 3 lines of code, easily implemented in a TM.
It is *exactly* the same logic as Cantor's diagonal proof that the Reals cannot be listed in their entirety. Cantor's proof doesn't show that the Reals are uncountable, any more than the same proof applied to computable numbers shows they are uncountable. It merely shows exactly what Cantor claimed; that you cannot explicitly list them. That they are also uncountable does not follow as a logical consequence.