"Tim Little" <tim@little-possums.net> wrote in message news:slrni1qn3c.jrj.tim@soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> 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." > > Most intuitive, and also least mathematically useful. However, we can > work with that. The input to the algorithm is the desired precision > and the output is a suitable approximant, correct? > > >> 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. > > 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.
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.
After all, nobody can write down the full decimal expansion of 1/3. But it is clearly computable, because it can be determined to any arbitrary degree of accuracy. The anti-diagonal is the same; even if we cannot write down the full infinite decimal expansion, we can compute it to any required degree of accuracy.
> The rest of your argument depends upon this non-algorithmic step, and > so is snipped.
Cantor provides an explicit algorithm for constructing (computing) the anti-diagonal.
> > > However, it occurs to me that your misunderstanding may be deeper than > I expected. Let's consider a simpler case: "lists" of length 1. > Suppose x is a real number, say Chaitin's Omega. Is x+1 computable? >
No. There is no algorithmic procedure for calculating omega+1q to arbitrary accuracy.
> If so, why? > > 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.
