>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."
That's too loose. It should be a an algorithm with *one* argument, the degree of precision required. An algorithm with two arguments doesn't count.
You can define an algorithm that takes two arguments, a list of computable reals, and a natural n, which returns a computable real that is not on the list. But that real is not necessarily computable by an algorithm that only has one argument.
>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 degree of accuracy, it is therefore computable.
You've described a computable function of *two* arguments: (1) the list, and (2) a natural n. For the antidiagonal to be computable, you must show that there is an algorithm that only takes one argument, a natural number n, and returns the nth decimal place of the antidiagonal.
>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 difference is that the antidiagonal of a list of reals returns a real that is not on the list. The antidiagonal of a list of computable reals does *not* necessarily return a computable real.
>The only difference is that I have to prove that the anti-diagonal >is also computable
which you haven't done. To prove that it is computable, you have to have an algorithm that takes one argument, n, and returns the nth decimal place of the real. You haven't shown that there is such an algorithm. You've shown that there is an algorithm that takes two arguments and produces the nth decimal place.
>but because Cantor's proof explicitly constructs the >anti-diagonal it is clearly computable
It's a computable function of *two* arguments. That doesn't mean that there is a computable function of *one* argument.
