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.
> Cantor's proof provides an explicit and simple algorithm to form > such a number, and it is extremely easy to compute.
If there exists no algorithm for computing the original list, how do you propose to use Cantor's proof to make an algorithm for the antidiagonal of that list?
>> It takes quite a bit of extra work (not part of Cantor's proof) to >> deduce that there is no computable list of all computable reals. > > Cantor's proof applied to computable numbers proves it immediately and > simply.
First you have to define the notion of "computable list", and set up the theorems proving properties about how computable lists and computable numbers relate.
>> I agree. It was Herc's deranged ramblings that brought computability >> into this discussion in the first place, when they really are >> completely irrelevant to Cantor's proof. >> >
> Well, they are relevant if you try and make the mental jump from > "cannot be listed" to "are therefore uncountable". This simply does > not follow.
It follows immediately from the definitions. You appear to have some bizarre definition of "list" that Cantor never used, employing concepts not developed until many decades later.
> The computable Reals cannot be listed either, but they are > definitely countable.
The computable reals can be listed and are countable.
> A Cantor construction applied to a purported list of all computable > Reals will identify a computable Real not on the list.
No, it will not.
> The diagonal is explicitly constructible given the list.
The definition of computable number does not include any presupposition of being supplied with infinite lists of infinite digit sequences. To be computable, a number must be constructible by a finite algorithm *without* being given the list. Don't take my word for it, look up the definition yourself.
