On 2010-06-21, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > "Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in message >> Not so - the "very simple algorithm" you are suggesting requires >> "the input list" in its raw (infinite) form as input. > > No. Computing the the anti-diagonall to n places only requires the > first n items on the list to n digits of accuracy.
Read the definition of computable real carefully, please!
You need to show that there exists a finite algorithm that accepts input n, with *no* additional input, and produces the n'th digit.
You don't get to put an upper bound on n when exhibiting the algorithm. The same algorithm must work for all n.
For some fixed M, you could embed M digits of the diagonal into the algorithm, and the algorithm would work for all n < M. But that's not enough: it has to work for all n.
> How is this number any less computable than the square root of 2?
There exists a straightforward algorithm (e.g. Newton's method) to calculate square roots to arbitrary precision. You can embed the value 2 into an algorithm which accepts n as input, and applies Newton's method to generate the first n digits of sqrt(2).
You cannot embed the list L into an algorithm which applies the antidiagonal procedure for arbitrary input n, as the list L is infinite. You can only embed finitely many digits of L, and so there will be an upper bound on the values of n for which the algorithm works.
> I don't use the whole list. To calculate the nth digit of the > anti-diagonal I only need the first n terms to n decimal places > accuracy. That is a finite amount of data.
However, you then need infinitely many different algorithms for increasing n. A number is only computable if the same algorithm works for all n.
>> Now IF you could codify all this data somehow into a finite >> program, so you had a computable function D(m,n) which produced the >> n'th digit of the m'th number in the list, you would be OK. But >> you DON'T have such a computable function D. > > Well, Cantor asks for a list of Reals. And D(m,n) is computable in > my case by definition
No, it is not. The m'th entry is computable for each m, with a different algorithm for every m. For D to be computable, there must exist a *single* finite algorithm that subsumes them all. There exists no such algorithm.
