"Mike Terry" <news.dead.person.stones@darjeeling.plus.com> wrote in message news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d@brightview.co.uk... > "Peter Webb" <webbfamily@DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1e2b53$0$316$afc38c87@news.optusnet.com.au... >> >> "Tim Little" <tim@little-possums.net> wrote in message >> news:slrni1r0ra.jrj.tim@soprano.little-possums.net... >> > On 2010-06-20, Peter Webb <webbfamily@DIESPAMDIEoptusnet.com.au> wrote: >> >> Explain to me how my requirements for the input list of all >> >> computable Reals is different to Cantor's requirements for the input >> >> list of all Reals, other than the requirement that every item on the >> >> list is computable? >> > >> > It is not. Your error comes later. >> > >> > Cantor's proof includes a construction taking a list L and defining an >> > antidiagonal real antidiag(L) from it. Your error is supposing that >> > this construction is a finite algorithm fitting the definition of >> > "computable real". It is not. By stretching the definition of >> > "algorithm" somewhat, it can be supposed to be an algorithm accepting >> > finite input n and infinite input L, and producing the n'th >> > antidiagonal digit. This is a stretch since algorithms are normally >> > not supposed to have infinite inputs. >> >> The calculation of the nth digit only requires the first n digits to n >> decimal places, and hence it is clearly a finite algorithm. >> >> Its simply ludicrous to suggest that the antidiagonal is not computable >> given that a very simple algorithm will explicitly churn it out. > > 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.
And it clearly is computable. I can compute it. I take the nth digit of the nth term, and ... blah blah.
How is this number any less computable than the square root of 2?
In both cases there is a finite algorithm to calculate the number to n decimal places for all n.
> As such, this is not an > algorithm that can be implemented on a Turing machine. I.e. the algorithm > is not the sort of algorithm that counts as "computable". Maybe you will > dispute this, but it's been explained to you several times (including one > of > my posts), and you can always go away and look up the definition of > computable function / Turing Machine etc., but it seems you've not done > this.
I don't have to look it up. I know it.
Obviously the anti-diagonal the computable. I can compute it to any required degree of accuracy using a very simple algorithm which explicitly computes it; you can't get much more computable than that.
> >> >> > >> > However, there is no way that you can then prove the existence of a >> > finite algorithm accepting only the *finite* input n and producing the >> > n'th antidiagonal digit. >> > >> >> Of course I can prove the existence of a finite algorithm. I can produce > it. >> >> To produce the nth decimal of the anti-diagonal, look at the first n >> items >> on the purported list of all computable Reals. > > There! Was I right, or was I right? :-)
How is looking at the first n digits of the first n terms and using Cantor's digit substitution to calculate the decimal place not computable?
> > There is an infinite amount of data on this "purported list", and you are > not allowed to base a computable function on an infinite amount of input > data. To do so shows you simply do not understand what computable means. >
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.
And, as a practical matter, if you want to give me a purported list of all computable Reals, I can actually calculate it to any required degree of accuracy in a finite number of steps.
> 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; which means we can always evaluate this function (as a computable Real must be able to be specified to any arbitrary degree of accuracy).
> What you DO have, is for each m, a computable function D_m (n) which > produces the n'th digit of the m'th number in the list. But how can you > use > these individual D_m in the definition of the antidiagonal? (You > can't...)
I do. If D(n,n)=1 then antidiagonal(n) = 2, else antidiagonal(n) = 1.
> > Do you not see this distinction? > > Knowing the existence of all the individual D_m is equivalent to knowing > that the list (sequence of numbers) consists of computable reals. > > Knowing the existence of D (which is a single computable function) is > equivalent to having a *computable* list of computable reals. >
Cantor's proof asks to see the list and then produces a number not on it.
Same as my proof.
Yes, that requires that te list be specified ... but Cantor's proof and mine are no different in that respect.
> Cantor's proofs do not require computable lists, they work with just any > old > lists... >
Indeed. And my proof requires computable Reals in a list. That is the difference.
>> Then substitute "1" for "2" >> blah blah. How is that not a finite algorithm? > > As explained it is not a finite algorithm because it uses as input an > infinite source of data. >
No, to specify the anti-diagonal to n places requires only a finite amount of data for all n, specifically the first n decimal places of the first n terms.
> By your reckoning every single real number is computable, because we can > have a TM that just accepts as input an infinite tape with the entire > digit > sequence encoded on it, and outputs that digit sequence.
No. I can explicitly calculate the nth decimal places with only n terms to n places of accuracy. No infinite input is required.
In any event, it is a farcical argument. Of course I can calculate the antidiagonal to any number of places of accuracy using only finite processes; Cantor's proof is constructive.
> > Surely you must be aware that this is NOT what computability means? >
Being able to specify the nth digit of a number in a finite number of steps for all n is a sufficient condition for compuatbility, and that is exactly what Cantor's diagonal proof provides - a means of calculating the nth digit of the anti-diagonal in a finite number of steps, using a finite input (the first n digits of the first n terms).
