Why can no one in sci.math understand my simple point?
in [Math]
|
Prev: power of a matrix limit A^n
Next: best way of testing Dirac's new radioactivities additive creation Chapt 14 #163; ATOM TOTALITY
From: Peter Webb on 19 Jun 2010 23:16 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qrf2.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> You haven't specified the list. I have to guess at some of the >> entries in the list, as I don't actually know and cannot determine >> which TMs halt. > > I have explicitly specified the list (which is actually a lot more > than Cantor's proof requires). It is not my problem whether you are > incapable of determining which TM's halt. It is a well-defined > mathematical function with all the properties assumed in Cantor's > proof. > No. Cantor's proof requires that the nth digit of the nth term can be determined. > Likewise the following is a valid list of binary digits: f(n) = 1 if > there are infinitely many prime pairs of the form (p, p+n), f(n) = 0 > otherwise. It doesn't matter whether or not you personally know the > value of f(2), or even whether there exists an algorithm to find out: > it is still a well-defined mathematical object. > > > Are you now starting to see the difference between the term "list" (as > used in Cantor's proof) and "recursively enumerable list" (as you are > using in yours)? > I am not using the term "recursively enumerable list" in my proof. Re-read it. I am asking for a list in *exactly* the same way as Cantor asks for a list, excepting that it contains only computable Reals and not just any Real. > - Tim
From: Peter Webb on 19 Jun 2010 23:17 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qrip.jrj.tim(a)soprano.little-possums.net... > On 2010-06-19, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Take the list, determine the nth digit of the nth item, blah >> blah. Remember, just as in Cantor's proof, you have to provide the >> list first. > > You don't get to "take the list" to compute the diagonal, as the list > is an infinite object in contradiction to the requirement of "finite > algorithm" in the definition of "computable real". > The anti-diagonal can be computed to any required degree of accuracy. There is an explicit construction for every digit in its decimal expansion. Try and tell me how it is uncomputable. > > - Tim
From: Peter Webb on 19 Jun 2010 23:24 "Daryl McCullough(" <stevendaryl3016(a)yahoo.com> wrote in message news:hvic840ge3(a)drn.newsguy.com... > Peter Webb says... > >>"Tim Little" <tim(a)little-possums.net> wrote > >>Hmmm. But you cannot provide me with a list of all Computable numbers, can >>you? Which is what Cantor's diagonal proof requires. > > Cantor's proof assumes the *existence* of such a list. It doesn't > assume that you know how to compute it. > If that is what you believe, then I am happy for the same rules to be applied to the purported list of all computable Reals. >>Of course there exists a mapping from N to computable numbers. >>But Cantor's proof requires more than that; it requires the >>mapping to be recursively enumerable such that we can also >>explicitly list them. > > No, it doesn't. If f is any mapping from N to computable numbers, > then antidiag(f) is a new real that is not in the image of f. > It doesn't matter whether f is recursively enumerable or not. > >>That a set cannot be listed is not the same as it is uncountable, > > I would say it this way: That a set is not recursively enumerable > does not imply that it is not enumerable. > Bingo. > The set of computable reals is enumerable, but not recursively > enumerable. The set of *all* reals is not enumerable. > Correct. >>You cannot give me a list of all Computable numbers, >>because I can use a diagonal construction to form a >>computable Real not on the list. > > If the list is computable, that's correct. If the list > is not computable, then that's not correct. > Cantor proved that you cannot compute a list of Real numbers. As you point out, this is not the same as being uncountable. >>Cantor's proof applied to Reals does *not* prove they are >>uncountable; > > It certainly does. If you assume that the set of reals is > countable, then that means that there is a bijection f from > the naturals to the reals. Cantor's proof shows that there > is no such bijection. > No. Exactly the same construction can be applied to a purported list of all computable Reals, but these are countable. >>> If that doesn't answer your question, you'll have to clarify what you >>> mean by it. >>> >> >>What I mean is that Cantor proved you cannot provide a list of all Reals. > > He proved that there is no bijection between the naturals and the reals. > By definition, that means that the reals are uncountable. > No, he proved that any purported list of all Reals must miss at least one Real. Which is exactly the same as what I prove for computable Reals. Yet the computable Reals are countable. Clearly his proof (in its orginal and common form) does not prove the Reals are uncountable. > -- > Daryl McCullough > Ithaca, NY >
From: Tim Little on 19 Jun 2010 23:27 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > Cantor's proof requires the purported list of all Reals to be > provided. That is your fantasy, not part of Cantor's proof. Cantor proved a closed-form proposition, which means that there are no free variables that can be "required to be provided". > No idea what you are talking about. Then perhaps you should read a reasonable reference on predicate logic and mathematical proof. > 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. 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. 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. > 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. > I am using Cantor's proof exactly, except for inserting the word > "computable" before every use of the word "real". That is the whole > point. That doesn't work because Cantor's work does not include any proof that antidiag(L) is computable: only that it is real. Hence there is a gaping hole in the validity of your modified text. You will not be able to fill that hole, because there are well-defined functions L for which antidiag(L) is *not* a computable real. There are even explicitly-definable such lists, and furthermore there are such lists where there are only two values in the range: for example, let L(n) = 0 if the n'th digit of Omega is 0, L(n) = 1/9 otherwise. Both members of range(L) are very obviously computable - they're even rational! But the decimal antidiagonal is not computable. - Tim
From: Owen Jacobson on 19 Jun 2010 23:50
On 2010-06-18 03:56:21 -0400, Peter Webb said: > "Tim Little" <tim(a)little-possums.net> wrote in message > news:slrni1m5c1.jrj.tim(a)soprano.little-possums.net... >> On 2010-06-18, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >>> If you can construct a list of all computable numbers (which you >>> can't), then Cantor's diagonal proof will construct a number not on >>> the list. And that number is definitely computable, because there is >>> a simple algorithm for producing it. Take the nth digit of the nth >>> item on the list >> >> That requires having the list be computable or provided as input, >> neither of which is assumed or proven. >> > > Cantor's proof that there can be no list of all Reals also requires the > list to be provided first. > > The form of the proof is identical - you give me a purported list of > all Reals with some property, and I prove the existence of at least one > Real which has that property which is not on the list, thus proving the > list did not contain all numbers with that property. Cantor used the > property "is Real", I used the property "is computable". > >> Rest snipped as it is based on your false premise. >> >> >> - Tim > > If you believe that you can list all computable numbers, you are > welcome to try and do so. Its a pointless exercise, as I can always > form a computable Real not on the list, but try anyway. Pick a G�del numbering scheme for the Turing machines. Then, given this scheme, the list of computable reals[0] is very simple: the n'th element of the list is the real produced by the real-computing Turing machine[1] with the n'th lowest G�del number (so the 0th element of the list is the real produced by the lowest-numbered machine, the 1st element of the list is the real produced by the next-lowest-numbered machine, and so on). Determining whether a Turing machine computes a real is not a computable problem, but that does not prevent such a list from existing. The antidiagonal of this list differs from every computable number, and there is a simple and effective algorithm for computing it *given the list*, but to show a contradiction you'd still have to prove that this number is computable in exactly sense [0] below. This is (likely) impossible, as this list itself is uncomputable, and the list can neither be embedded in a Turing machine's transition function[2] directly nor stored on the tape[3]. More formal definitions of "computable number" would make the necessary step in proving your argument even harder. -o [0] A real is computable if and only if there is a Turing machine that computes it[1]. [1] A Turing machine computes a real r if and only if, starting with an encoding of some natural number m on its tape, it halts with an encoding of the m'th digit of r on the tape. [2] Keeping in mind that a Turing machine has finitely many states Q and finitely many symbols L, the image of the transition function contains at most |Q| * |L| elements -- far too few to encode an infinite list of reals. [3] At every step, a Turing machine has only finitely-many non-blank cells on the tape -- far too few to encode an infinite list of reals. |