>> Perhaps if you could explain how my proof differs from Cantor's >> proof, that would be a start. > > I have done already, but perhaps I can explain it in different terms > for you. > > >> You seem to accept Cantor's proof, but not mine. Yet they are almost >> identical, the only difference being I have inserted the word >> "computable" in front of "reals". >> >> I can't see how you can accept one and not the other. > > Cantor's proof shows that for any mapping L:N->R, antidiag(L) is real > and not in range(L). Cantor's proof does include a proof that > antidiag(L) is real. It does not show that antidiag(L) is a > computable real. >
Yes.
> You cannot just drop "computable" in there and suppose that the logic > works, just as you cannot drop "rational" in there and suppose that > the logic works. >
Well, it does work.
> If you want to prove that for any mapping L:N->R, antidiag(L) is > computable, you need to include a proof that antidiag(L) satisfies the > mathematical definition for a computable real. >
OK.
I an specify it to n places for all n using the following simple algorithm.
Change the nth digit of the nth term from a 1 to a 2 and else to a 1.
Thus if your list contained say:
.1111111 .2222222 .1111222
The antidiagonal is 0.212...
Notice that I computed this quite easily?
Every item on the list is computable. So every item is known to at least n decimal places of accuracy, and Cantor gives us a very easy way to compute the first n terms on the anti-diagonal given the first n items on the list to n decimal places.
> >> It is extremely easy to compute. >> >> Take the nth decimal place of the nth term. > > The nth decimal place of the nth term of what? The list L? That's > fine if you permit infinite lists of reals as input to the algorithm, > but the definition of "computable real" permits no such thing. >
No, to calculate the first n terms of the anti-diagonal you require only te first n items on the list to n places of accuracy.
Cantor's anti-diagonal is computable because the first n items on the list are computable, and he provides an explicit contruction for his number which is very easy to compute indeed.
> >> I am using Cantor's proof exactly, except for inserting the word >> "computable" before every use of the word "real". That is the whole >> point. > > That doesn't work because Cantor's work does not include any proof > that antidiag(L) is computable: only that it is real. Hence there is > a gaping hole in the validity of your modified text.
Well, no. Cantor actually provides an explicit construction for the anti-diagonal. He does have to prove its a computable number; he actually computes it.
If every item on the list is computable, every item can be specified to any required degree of accuracy (in decimal, in this case), and we can "compute" the nth decimal place of each. Clearly we can compute the Cantor substitution to explicitly construct another number, the anti-diagonal. Simply substituting a "1" fo a "2" etc is still computable.
> > You will not be able to fill that hole, because there are well-defined > functions L for which antidiag(L) is *not* a computable real. > There > are even explicitly-definable such lists, and furthermore there are > such lists where there are only two values in the range: for example, > let L(n) = 0 if the n'th digit of Omega is 0, L(n) = 1/9 otherwise. >
I am having a bit of trouble computing even the first term of that. I am also wondering how Cantor would have felt about that. I can't see that he can change a "1" to a "2" etc if he doesn't know what the value is.
But you have made an excellent point in your example. When Cantor is confronted with some digit as poorly defined your Chaitan's number example, it can simply say "I don't care what the number actually is". There is not the same luxury with computable Reals; this act of arbitrary/random choice can make them uncomputable, as your example shows.
> Both members of range(L) are very obviously computable - they're even > rational! But the decimal antidiagonal is not computable. >
Well, yes, but I am failing to see how you are providing a list of computable Reals when you won't actually tell me even what is the first computable Real on the list.
Cantor's algorithm requires slightly more than a set of Reals, it also demands they are ordered for us - there is a mapping from N to that set. He asks for and uses in his proof a "list" of numbers. What number does 1 map to in your example?
> > - Tim
That's still a nice example, that every item in a list can be computable but the anti-diagonal is not. But I still don't think you are really playing fair with this one. You have to tell me what the first, second, third etc items are on the list. I mean, that's what a list is after all, a mapping from N, and that is what Cantor's proof requires as input.
