"Tim Little" <tim@little-possums.net> wrote in message news:slrni1mcki.jrj.tim@soprano.little-possums.net... > On 2010-06-18, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> Of course this number is computable; there >> is a simple algorithm to compute it. > > I see you still haven't consulted a definition of "computable number".
Umm, yes I have.
> No worries, let me know when you have. > > > - Tim
There can be no list of all computable numbers.
The proof is quite simple. Lets imagine that you have such a list of all computable numbers.
Lets say it starts off ...
.111111... .141592 ... .71828 ...
Take the 1st digit of the first number. If it is a "1", then make the first digit of the diagonal number "2", otherwise make it a "1". Well, the first digit of the first number is a "1", so the first digit of the diagonal number is a "2".
Now take the second digit of the second number and do the same substitution. Its a "4", so the second digit of the diagonal number is "1".
Now take the 3rd digit of the 3rd number ... its a "8", so the third digit of the diagonal number is a "1".
Continue in this fashion.
The number that is produced is clearly "computable", because we have computed it. Its also clearly not on the list. Therefore the list cannot have contained all computable numbers.
Exactly the same as Cantor's proof that the Reals cannot be listed.
However, this does *not* mean that there are an uncountable number of them. The computable numbers are countable.
And similarly Cantor's proof does not show that there are an uncountable number of Reals. It proves exactly what Cantor claimed it did, which is that you cannot list all Reals.
