Why can no one in sci.math understand my simple point?
in [Logic]
|
From: Peter Webb on 20 Jun 2010 20:16 "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:B8WdnX3itoZ7zYPRnZ2dnUVZ7qednZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1e2b53$0$316$afc38c87(a)news.optusnet.com.au... >> >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1r0ra.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-20, Peter Webb <webbfamily(a)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). > Regards, > Mike. > > >
From: Peter Webb on 20 Jun 2010 20:20 "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:dLGdnUdTkbKpzoPRnZ2dnUVZ8hKdnZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1e3743$0$1028$afc38c87(a)news.optusnet.com.au... >> >> Perhaps if you could explain how my proof differs from Cantor's >> >> proof, that would be a start. >> > >> > I have done already, but perhaps I can explain it in different terms >> > for you. >> > >> > >> >> You seem to accept Cantor's proof, but not mine. Yet they are almost >> >> identical, the only difference being I have inserted the word >> >> "computable" in front of "reals". >> >> >> >> I can't see how you can accept one and not the other. >> > >> > Cantor's proof shows that for any mapping L:N->R, antidiag(L) is real >> > and not in range(L). Cantor's proof does include a proof that >> > antidiag(L) is real. It does not show that antidiag(L) is a >> > computable real. >> > >> >> Yes. >> >> > You cannot just drop "computable" in there and suppose that the logic >> > works, just as you cannot drop "rational" in there and suppose that >> > the logic works. >> > >> >> Well, it does work. >> >> > If you want to prove that for any mapping L:N->R, antidiag(L) is >> > computable, you need to include a proof that antidiag(L) satisfies the >> > mathematical definition for a computable real. >> > >> >> OK. >> >> I an specify it to n places for all n using the following simple > algorithm. >> >> Change the nth digit of the nth term from a 1 to a 2 and else to a 1. >> >> Thus if your list contained say: >> >> .1111111 >> .2222222 >> .1111222 >> >> The antidiagonal is 0.212... >> >> Notice that I computed this quite easily? >> >> Every item on the list is computable. So every item is known to at least >> n >> decimal places of accuracy, and Cantor gives us a very easy way to >> compute >> the first n terms on the anti-diagonal given the first n items on the >> list >> to n decimal places. >> >> >> > >> >> It is extremely easy to compute. >> >> >> >> Take the nth decimal place of the nth term. >> > >> > The nth decimal place of the nth term of what? The list L? That's >> > fine if you permit infinite lists of reals as input to the algorithm, >> > but the definition of "computable real" permits no such thing. >> > >> >> No, to calculate the first n terms of the anti-diagonal you require only > te >> first n items on the list to n places of accuracy. > > So you require as input: > - the 1st digit to 1 place of accuracy > - the 2nd digit to 2 places of accuracy > - the 3rd digit to 3 places of accuracy > - ... > > The ... above is the give away! For your algorithm to work its going to > require an INFINITE amount of input data. (Remember, you are trying to > find > a SINGLE stand-alone FINITE algorithm that produces ALL the required > digits > of the antidiagonal.) > No, I only need a finite algorithm which will calculate it to n decimal places with finite input. The definition of computable only requires me to produce it to arbitrary accuracy. I'm pretty sure you can't produce an algorithm which will produce *every* digit in sqrt(2) in finite time. Sqrt(2) is computable because we can calculate it to arbitrary accuracy, not because we can explicitly list every digit in its decimal expansion in finite time; we can't. > So Tim was quite right, and you haven't answered his point correctly > yet... > > Regards, > Mike. > >
From: Peter Webb on 20 Jun 2010 20:23 "Jesse F. Hughes" <jesse(a)phiwumbda.org> wrote in message news:87wrttxsgx.fsf(a)phiwumbda.org... > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> writes: > >> "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message >> news:4c1e3743$0$1028$afc38c87(a)news.optusnet.com.au... >>> No, to calculate the first n terms of the anti-diagonal you require only >> te >>> first n items on the list to n places of accuracy. >> >> So you require as input: >> - the 1st digit to 1 place of accuracy >> - the 2nd digit to 2 places of accuracy >> - the 3rd digit to 3 places of accuracy >> - ... >> >> The ... above is the give away! For your algorithm to work its going to >> require an INFINITE amount of input data. (Remember, you are trying to >> find >> a SINGLE stand-alone FINITE algorithm that produces ALL the required >> digits >> of the antidiagonal.) >> >> So Tim was quite right, and you haven't answered his point correctly >> yet... > > No, you fail to understand the brilliance that Peter brings to this > conversation. > > Every real is computable. You just have to produce a finite amount of > data to compute the real to n digits, namely, the first n digits of the > real you want to compute. > If that is true for all n, then your statement is true. If you can calculate the nth digit of a Real for all n, then the Real is computable. Unfortunately its not true. > All of you naysayers are just holding back inevitable progress. > Perhaps if you were to look at the substance of the proof, rather than just heckling ... > -- > "And yes, I will be darkening the doors of some of you, sooner than you > think, even if it is going to be a couple of years, and when you look > in my eyes on that last day of work at your school, then maybe you'll > understand mathematics." -- James S. Harris on Judgment Day
From: Peter Webb on 20 Jun 2010 20:28 "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:a_mdnZe4xaoOxIPRnZ2dnUVZ8umdnZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1d86f0$0$18229$afc38c87(a)news.optusnet.com.au... >> >> "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in > message >> news:NNqdnTtg2LuExoDRnZ2dnUVZ8lKdnZ2d(a)brightview.co.uk... >> > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message >> > news:4c1c6be3$0$17177$afc38c87(a)news.optusnet.com.au... >> >> >> >> "Tim Little" <tim(a)little-possums.net> wrote in message >> >> news:slrni1om15.jrj.tim(a)soprano.little-possums.net... >> >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> > wrote: >> >> >> So Cantor's proof when applied to computable Reals proves exactly >> >> >> what in your opinion? >> >> > >> >> > That there is a real not on the list. >> >> > >> >> > >> >> >> I might remind you that as the form of proof is identical to that >> >> >> used by Cantor for all Reals, whatever you believe that Cantor's >> >> >> proof applied to computable Reals proves, his proof applied to all >> >> >> Reals must prove the same thing. >> >> > >> >> > It does prove exactly the same thing: in both cases, all such lists >> >> > omit at least one real. >> >> > >> >> > >> >> >> Its the same proof, after all, except limitting the set to just >> >> >> computable Reals. >> >> > >> >> > No, there is a slight difference: the antidiagonal is a real number. >> >> > It does not necessarily produce a computable real number. >> >> > >> >> >> >> Of course it is computable. Cantor provides a simple construction for > the >> >> number. >> > >> > No, you're misunderstanding the meaning of computable. >> > >> > Hopefully you will be OK with the following definition: >> > >> > A real number r is computable if there is a TM (Turing machine) >> > T which given n as input, will produce as output >> > the n'th digit of r. >> > >> > So let us suppose there is a list L (not a "computable list", just a >> > "list") >> > of computable numbers in [0,1], covering all computerable numbers. >> > >> > [You have your own strange definition of "list", but I am using the >> > term >> > with it's standard mathematical meaning: L is just a function mapping >> > N >> > (natural numbers) to CR (computable reals). Perhaps we should also > insist >> > that lists are injections (no duplicates) - that's fine. YOU seem to > want >> > to define "list" to only include "computable" functions from N to CR, > but >> > that is NOT what everybody else (including Cantor) means by "list"!] >> > >> > L : N --> CR >> > >> > so we have the sequence (=list) of computable reals: >> > >> > ( L(0), >> > L(1), >> > L(2), >> > ....) >> > >> > Each computable real has it's digital representation, so this list can > be >> > written: (using d(m,n) for n'th digit of L(m) >> > >> > L(0) digits : d(0,0), d(0,1), d(0,2), ... >> > L(1) digits : d(1,0), d(1,1), d(1,2), ... >> > L(2) digits : d(2,0), d(2,1), d(2,2), ... >> > ... >> > >> > Now, given m and n, is there necessarily a TM that can take m and n as >> > inputs, and ouput d(m,n)? >> > >> > Well, each L(m) individually is computable: there is a corresponding >> > TM, >> > TM_m such that given n as input it will compute d(m,n). We could say: >> > >> > TM_m (n) = d(m,n) >> > >> > But all the TMs can be different and completely unrelated to each >> > other. >> > >> > Can we say there will always be a *single* TM TM_ALL_m, which >> > "subsumes" >> > all >> > the TM_n, i.e. if given m and n as input, will compute d(m,n)? I.e. >> > >> > for all m,n: TM_ALL_m (m,n) = d(m,n) ????? >> > >> > Unfortunately for your argument, the answer is NO. >> > >> > But that is exactly what you would need to argue that the anti-diagonal > is >> > computable: You need a TM that could calculate d(m,m), but this needs > the >> > TM TM_ALL_m, and we do not have that! >> > >> > I know what you want to say at this point! :) You want to say that I > have >> > "explicitly given you" d(m,n), and I can only do this if d(m,n) is >> > computable. (Right?) And you want to tell me that Cantor's diagonal >> > proof >> > is the same? >> > >> > Well, this is a misreading of Cantor's proof! Look closely: >> > >> > Paraphrasing of Cantor's proof: >> > >> > Given a function L: N --> [0,1], there >> > exists r in [0,1], such that >> > for all n, r != L(n) [i.e. r is not in the list] >> > >> > Proof: >> > 1) Suppose L: N-->R >> > 2) Define LD: (NxN)-->{0,1,2,3,4,5,6,7,8,9} >> > such that LD(m,n) = n'th digit of L(m) >> > 3) Define RD: N-->R >> > such that RD(m) = [...antidiagonal digit m...] >> > 4) Then RD determines a real r in [0,1] >> > 5) Show for all n, r != L(n) from defn. of r above. >> > >> > Where in this proof does Cantor require LD(m,n) to be computable? > (Answer >> > = >> > nowhere.) >> > >> > I think maybe you are thinking it must be computable, due to your >> > misleading >> > use of the phrase "explicitly given", but actually all Cantor does is >> > argue >> > that IF a (any) function L (not necessarily computable) EXISTS mapping >> > N >> > to >> > [0,1], the mere existence of L implies the existence of a corresponding >> > real >> > r not in the list L. There is nothing requiring real computer programs > to >> > actually compute anything here! It's just a mathematical proof of >> > existence >> > of something. >> > >> >> What you are writing above is *not* Cantor's diagonal proof as it appears > on >> a million websites. > > Well, I claim that it is at least OBVIOUSLY EQUIVALENT to what Cantor is > saying. It's true I didn't go to a web site and cut and paste any > "official" text from his original document, but in essence my > understanding > is: > > 1. Cantor shows that any map from N to R cannot be "onto" R. > 2. That my proof above sketches this out: > - Cantor equates real numbers with their digit sequences > (This is why I go from L to LD) > - Cantor shows the existence of a new digit sequence, via > the antidiagonal argument > (That is what I do in step (3). RD is my new digit sequence.) > - Cantor proves that RD is a new digit sequence > - and that consequenctly the corresponding real number > is not in the original map L. > > So I think my proof follows Cantor's pretty closely, although it is my own > notation. Given the amount of effort I put into trying to help you, I'm > disappointed you can't get over some minor notationaly differences to > follow > what I'm saying. The whole point of what I am doing is to use his original proof in its original form. Introducing new notation is a crank's way of arguing. Why not look at my proof, which follows Cantor's proof, instead of changing te notation to produce a proof which you claim is equivalent and arguing about that different proof, which you claim differs only in notation? > You've also given no indication of in what way you think > my proof differs from Cantors! (Well, that would be OK if my proof was > "nothing like" Cantor's but that's clearly not the case as I've just > explained, so I'm left mystified by your claim...) > >> >> The whole point of my post was to use Cantor's proof exactly, which alows > me >> to demonstrate that Cantor's proof does *not* in of itself prove the >> uncounatbility of the Reals. >> >> Perhaps if you were to tell me where you think the error in my very >> simple >> proof is, then we would be making progress. > > Sure I'll do this. To avoid a further "that's not Cantor's proof" claim > from you, please quote exactly what proof of Cantor's you want me to > comment > on. > There can be no list of all Reals. Imagine such a list of purported Reals exists. Compute the anti-diagonal number as follows ... blah blah. This Real is not on the list. > Regards, > Mike. > > > >
From: Peter Webb on 20 Jun 2010 20:31
"Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message news:E4GdnSMEFu3jxoPRnZ2dnUVZ8m2dnZ2d(a)brightview.co.uk... > "Peter Webb" <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote in message > news:4c1d8758$0$14086$afc38c87(a)news.optusnet.com.au... >> >> "Tim Little" <tim(a)little-possums.net> wrote in message >> news:slrni1qqsn.jrj.tim(a)soprano.little-possums.net... >> > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> >> Of course it is computable. Cantor provides a simple construction >> >> for the number. >> > >> > Only if the list itself is a recursively enumerable function. >> > Cantor's proof makes no such assumption. >> > >> >> Yes it does. It requires that the nth digit of the nth term can be >> calculated. > > Not so - the proof simply needs the n'th digit of the n'th term to EXIST. Of course the nth digit of the nth term exists. Or are you claiming there are computable Reals which don't have decimal expansions? > It is then possible to prove the EXISTENCE of the missing real number (via > the antidiagonal argument). His proof should not be read as instructions > for a "C" program or some such! :-) It's an existence proof, not really > an > "algorithm" at all in the sense I would use the word... Of course it is an algorithm. It accepts the first n digits of the first n terms on the list and computes the anti-diagonal to n decimal places for all n. > > >> This is not quite as strong as being re, but it is close. In any >> event, it is exactly the same restriction as I place on the purported >> list >> of all computable Reals. > > No, you require the list itself to be computable, so that given m,n as > input > you can compute "the n'th digit of the m'th number". That's MUCH more > than > Cantor requires. Cantor's proof uses the nth digit of the nth term to find a Real not on the list. > >> >> > >> > - Tim >> > > |