"Virgil" <Virgil@home.esc> wrote in message news:Virgil-20BC96.00395219062010@bignews.usenetmonster.com... > In article <4c1c6011$0$17176$afc38c87@news.optusnet.com.au>, > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <tim@little-possums.net> wrote in message >> news:slrni1okg1.jrj.tim@soprano.little-possums.net... >> > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> >> "Tim Little" <tim@little-possums.net> wrote in message >> >>> Your "simple fact" is simply wrong. Look up the definition of >> >>> "computable real" and get back to us. >> >> >> >> Why? >> > >> > Because you clearly don't know how a computable real is defined. >> > >> > >> >> If you believe there is an error in what I have said, identify it. >> > >> > I have, many times now. >> > >> > >> >> Or give me at least a hint. As a start, my argument rests on two >> >> observations: >> >> >> >> 1. Cantor's diagonal construction, when applied to a purported list >> >> of all computable Reals, will produce a computable Real not on the >> >> list. >> > >> > The latter part is incorrect. It produces a real, but not a >> > computable real. If you believe otherwise, provide a proof that the >> > antidiagonal real is computable. >> > >> >> Well, there are lots of definitions of a computable Real, I will use >> Wikipedia's most intuitive definition: "computable reals, are the real >> numbers that can be computed to within any desired precision by a finite, >> terminating algorithm." >> >> 1. Given a list of computable Reals, we can identify the nth computable >> Real >> on the list by simply counting down to the nth entry. >> >> 2. Given the nth computable Real on the list, we can count off and >> identify >> the nth digit of this Real. >> >> 3. With the nth digit of the Real, we can use Cantor's construction to >> identify the nth digit of the anti-diagonal. >> >> 4. As we can specify every digit in the anti-diagonal explicitly and to >> any >> desired degre of accuracy, it is therefore computable. > > But that requires that the list be given in advance, so that > "anti-diagonal" is not really a single number so much as a function from > lists to numbers with value depending on the particular list being > chosen. So I am not quite confident that that situation qualifies as a > computable number, which should not, in my mind, be dependent on a > particular list of numbers being given. >
Cantor's proof that Reals cannot be listed requires an explicit list, such that the nth digit of the nth term can be determined.
My proof follows exactly the same form.
>> >> 5. But the anti-diagonal number does not appear on the list. >> >> 6. Therefore, the list could not have included all computable Reals. >> >> Exactly the same as Cantor's proof that the Reals cannot be listed. The >> only >> difference is that I have to prove that the anti-diagonal is also >> computable, but because Cantor's proof explicitly constructs the >> anti-diagonal it is clearly computable (as long as every item in the list >> is >> computable, which is the starting assumption which we prove to be >> incorrect, >> just like in Cantor's original proof). > > Actually not. The starting assumption had better be that list contains > EVERY computable number if you are trying to prove something INcorrect. >
That is the premise in Cantor's original proof - that it contains every Real - and this is the premise in my slight reworking of it - that it contains every computable Real.
> It is perfectly possible to have lists of computable numbers which are > not complete in which case the anti-diagonal construction proves nothing.
Indeed. And its perfectly possible to have lists of Reals which are not complete in which Cantor's construction proves nothing.
Cantor's proof starts with a purported list of all Reals; I start with a purported list of all computable Reals.
The proof is *exactly the same*; that's the whole point, if it was different it would not prove that just because a set cannot be explicitly listed does not imply it is uncountable. What Cantor proved (in more modern parlance) is that there is no recursively enumerable function from N -> R. That is not the same as the set is uncountable. There is no r.e. function N -> computable Reals, but these are still countable.
