On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <email@example.com> wrote in message >> That is only a "finite, terminating algorithm" if the list is finite. >> Since the only input to the algorithm is the desired precision, your >> recipe only works if you can embed the list into the algorithm. > > No. You could level the same argument against Cantor's original proof.
No you couldn't, as it makes no assumption of any finite algorithm. Only *your* alteration of Cantor's proof assumes any sort of finite algorithm, as it is required for the definition of "computable real".
> For a number to be computable, it must be able to be calculated to > any required degree of accuracy (according to the definition we have > just both agreed on). This is obviously true of the anti-diagonal.
Only if the list is computable, which Cantor's proof does not require.
> Cantor provides an explicit algorithm for constructing (computing) > the anti-diagonal.
No, the proof only provides an algorithm fragment. A full algorithm for a computable real must take the precision as input, and nothing else. The constructive portion of Cantor's proof takes an infinite list of real numbers as "input", and so is not a valid algorithm for a computable real.
>> If not, how does this differ from "suppose L is a list of real >> numbers. Is antidiag(L) computable?" > > Because there is an algorithmic procedure for calculating the > anti-diagonal to any required degree of accuracy.
If you are given L, you say you can compute antidiag(L) regardless of what L is. If you are given x, can you not compute x+1 regardless of what x is? By your argument, does this not mean that x+1 is always a computable real?