Peter Webb says... > > >"Tim Little" <tim@little-possums.net> wrote in message
>> The relevant point: the *only* input to the Turing machine in the >> definition is n. The rest of the tape must is blank. Peter >> apparently believes that a number is still computable even if the >> Turing machine must be supplied with an infinite amount of input (the >> list of reals). >> > >No.
You said that you believed that if L is any list of computable reals, then antidiag(L) is computable. That's not true. It's only true if L is computable.
Imagine that you have a Turing machine with two tapes: The first tape holds a list L of computable reals. The second tape holds a natural number, n.
Then you can certainly program the Turing machine so that the output is the nth decimal place of the anti-diagonal of L. That doesn't mean that the antidiagonal is a computable real.
For it to be a computable real, there has to be a Turing machine with only *one* input Tape, which contains a natural number, n. The Turing machine would have to output the nth decimal place of the antidiagonal *without* access to the original list L. In general, that's impossible.
So there is a two-tape Turing machine that can compute the antidiagonal, but there is no one-tape Turing machine. So the antidiagonal is not computable, in general.
>You seem to agree that the computable Reals are countable.
Yes.
>Do you agree that Cantor's diagonal proof when applied to a >purported list of all computable Reals will produce a computable Real >not on the list,
No. It produces a *real* not on the list, not necessarily a computable real.
Imagine a Turing machine tape T that contains a list of computable reals. There are various ways that a tape could contain a list of computable reals, but one way is this: The list contains a list of integers, each integer is a code for a Turing machine program for computing a real.
Now, given the tape T above, you can write a Turing machine that computes the antidiagonal of T. But that *doesn't* mean that the antidiagonal is a computable real. For it to be computable, there has to be a Turing machine program that computes it *without* any auxiliary tapes such as T.
Now, if T itself were computable, then the Turing machine could compute T, and then use T to compute the antidiagonal. But if T is not computable, then you can't compute the antidiagonal.
