In article <firstname.lastname@example.org>, "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote:
> "Tim Little" <email@example.com> wrote in message > news:firstname.lastname@example.org... > > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > >> "Tim Little" <email@example.com> 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.
> > 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.
It is perfectly possible to have lists of computable numbers which are not complete in which case the anti-diagonal construction proves nothing. > > > > HTH > > Peter Webb