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 20 Jun 2010 20:37 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-B10127.13553420062010(a)bignews.usenetmonster.com... > In article > <7d59f93c-4bc8-43e2-9b40-485733a01305(a)z8g2000yqz.googlegroups.com>, > WM <mueckenh(a)rz.fh-augsburg.de> wrote: > >> On 20 Jun., 01:58, Tim Little <t...(a)little-possums.net> wrote: >> > On 2010-06-19, Virgil <Vir...(a)home.esc> wrote: >> > >> > > There is, however, some question in my mind about the existence of a >> > > list of all and ONLY computable reals. >> > >> > Why? The computable reals can be proven countable, as you already >> > know, so there is a bijection between N and the set of countable >> > reals. >> >> That is not true. An exclusive list need not exist. >> >> The reals in a certain Cantor-list are countable. And if you form the >> anti-diagonal of that list and add it (for instance at first position) >> to the list, this new list is also countable. Again consttruct the >> anti-diagonal and add it to the list. Continue. The situation remains >> the same for all anti-diagonals you might want to construct. Therefore >> all reals constructed in that way are countable. Nevertheless it is >> impossible to put all of them in one list, because there would be >> another resulting anti-diagonal. >> >> Conclusion: It is impossible to obtain a bijection of all these reals >> with N although all "these" reals are countable with no doubt. > > > Equal cardinality of two sets requires, by definition, a bijection > between them. > > The naturals are, by definition of COUNTABLE cardinality so that any set > of equally countable cardinality must have a bijection with the > naturals. > > Cantor has shown that the set of all reals cannot biject with the > naturals, ergo, the set of all reals is NOT of countable cardinality. > Actually, he shows that any purported list of all Reals must miss at last one Real. *not* the same as being uncountable, witness the same argument applied to computable Reals. > Actually Cantor's original "diagonal" proof was based on the set of all > functions from the naturals to a two element set, No. It is based upon showing that any purported list of all Reals must neccesarily omit at least one Real, and he does this by providing an explicit construction of the anti-diagonal based upon examining the first n digits of the first n items on the list for all n. Which is exactly what I am doing. > but several people > have constructed bijections between that set of functions and the set of > all reals. I have done it myself. Perhaps if you were to provide an actual list of all computable numbers - and only the computable numbers - your claim that they can be listed would be vindicated. My bet is that you will have about as much success forming a list of all computable Reals as you would do forming a list of all Reals, but if you think such a list exists, go for it.
From: Peter Webb on 20 Jun 2010 20:39 "Virgil" <Virgil(a)home.esc> wrote in message news:Virgil-22B7E6.14010020062010(a)bignews.usenetmonster.com... > In article > <ccb88bb1-d8a6-4f04-bc6a-ca3346f7c8ad(a)c10g2000yqi.googlegroups.com>, > WM <mueckenh(a)rz.fh-augsburg.de> wrote: > >> On 20 Jun., 02:04, "Mike Terry" >> > >> > 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. >> >> Whatever might be the true meaning: The Turing machine need a finite >> definition. Therefore the computable number has a finite definition. >> >> There are only countable many finite definitions. And every diagonal >> of a defined Cantor list has also a finite definition. > > Cantor's argument does not require that any member of a list of reals be > computable beyond a finite number of decimal places, so enough of each > can be finitely defined for the proof to work. Exactly the same as mine. Cantor calculates the anti-diagonal to n places (for all n) using only the first n digits of the first n items. So do I.
From: Tim Little on 20 Jun 2010 20:40 On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Tim Little" <tim(a)little-possums.net> wrote in message >> 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. In what way is that "a finite algorithm accepting only the *finite* input n"? It either must embed the list within the algorithm (thus rendering it not finite), or accept the list as additional ainput (thus violating the condition that it accept only the finite input n). > Well, I think I am making a pretty good hand of my case. But yes, I > know what I am saying is not accepted. I am genuinely confused by > this - the fact that my opinions are unique, and I would expect > therefore to be almost certainly wrong (with probability 1). On the > other hand my argument seems pretty solid to me. Read through very carefully the definition of a computable real, perhaps also reading some of the other known results on computable reals and following their proofs. At some point you will hopefully see why the "construction" in Cantor's diagonal proof does not qualify as a finite algorithm in the sense of the definition of computable real. - Tim
From: Tim Little on 20 Jun 2010 20:45 On 2010-06-20, Mike Terry <news.dead.person.stones(a)darjeeling.plus.com> wrote: > Not so - the "very simple algorithm" you are suggesting requires > "the input list" in its raw (infinite) form as input. As such, this > is not an algorithm that can be implemented on a Turing machine. (According to some definitions of Turing machine it can, as some definitions permit the input present on the tape initially to be arbitrary, including having infinitely many nonblank cells) I agree that it certainly does not fit the more restricted type of Turing machine permitted in the definition of computable real, as those permit only a finite input. That input is a specification denoting precision, digit number, or similar depending on exactly which definition of computable real is employed. - Tim
From: Tim Little on 20 Jun 2010 21:07
On 2010-06-21, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: > "Mike Terry" <news.dead.person.stones(a)darjeeling.plus.com> wrote in message >> 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. Read the definition of computable real carefully, please! You need to show that there exists a finite algorithm that accepts input n, with *no* additional input, and produces the n'th digit. You don't get to put an upper bound on n when exhibiting the algorithm. The same algorithm must work for all n. For some fixed M, you could embed M digits of the diagonal into the algorithm, and the algorithm would work for all n < M. But that's not enough: it has to work for all n. > How is this number any less computable than the square root of 2? There exists a straightforward algorithm (e.g. Newton's method) to calculate square roots to arbitrary precision. You can embed the value 2 into an algorithm which accepts n as input, and applies Newton's method to generate the first n digits of sqrt(2). You cannot embed the list L into an algorithm which applies the antidiagonal procedure for arbitrary input n, as the list L is infinite. You can only embed finitely many digits of L, and so there will be an upper bound on the values of n for which the algorithm works. > 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. However, you then need infinitely many different algorithms for increasing n. A number is only computable if the same algorithm works for all n. >> 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 No, it is not. The m'th entry is computable for each m, with a different algorithm for every m. For D to be computable, there must exist a *single* finite algorithm that subsumes them all. There exists no such algorithm. - Tim |