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 11:52 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1qvhp.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> Cantor's proof that Reals cannot be listed requires an explicit >> list, such that the nth digit of the nth term can be determined. > > No, it just requires that the nth digit of the nth term exist. It > does not require that the nth digit of the nth term be computable by a > finite algotihm. It does not even require that there is a finite > mathematical formula defining it. > > >> What Cantor proved (in more modern parlance) is that there is no >> recursively enumerable function from N -> R. > > False on three counts: > > 1) Recursive enumerability has nothing to do with it. > So you assert. Personally, I think that the fact that the computable Reals are not recursively enumerable is intimately related, as a set being recursively enumerable in this context basically means the same thing as there being a mapping from N to exactly that set, ie a list of elements. It is so intimately related as to being different words for the same thing. > 2) The word you should be using instead of "recursively enumerable" > is "surjective". > Well, recursively enumerable is a property of sets, and surjective is a property of mappings, so dunno what you are talking about. > 3) There are plenty of recursively enumerable functions from N -> R. > I don't dispute that. > Please, learn how to understand mathematical proofs so that you don't > embarrass yourself further in future. > Well, that's very rude of you. > > - Tim
From: Jesse F. Hughes on 20 Jun 2010 11:51 Newberry <newberryxy(a)gmail.com> writes: > On Jun 19, 6:06 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> Newberry <newberr...(a)gmail.com> writes: >> >> Because every infinite sequence of digits represents a real number? And >> >> the antidiagonal is one such sequence? >> >> > If it does not exist then it does not represent anything let alone a >> > number. >> >> > Now it is clear that it does not exist. Since all the reals are on the >> > list and the anti-diagonal would differ from any of them. This >> > violates the assumption. Hence the anti-diagonal does not exist. >> >> Wow. Are you saying that the *sequence of digits* specified by the >> anti-diagonal does not exist? > > That's right. There is no formula or algorithm to construct the list. > It means that you would have to flip each and every digit one by one. > And that is impossible. Of course, it is perfectly reasonable to accept that there is no such list, because Newberry says so. Cantor was this utterly insane freak who chose not to accept Newberry's word for it, and instead *prove* that there was no list of all real numbers. Obviously, his proof is nonsense, because, after all, Newberry said there was no list. -- "I suggest to those who listen that they enjoy the world, whatever their piece of it may be, as much as they can over the next few days, as soon enough, it will pass away, thanks to people who call themselves 'mathematicians'." -- JSH envisions geek Ragnarok
From: Peter Webb on 20 Jun 2010 12:03 "Tim Little" <tim(a)little-possums.net> wrote in message news:slrni1r53f.jrj.tim(a)soprano.little-possums.net... > On 2010-06-20, Peter Webb <webbfamily(a)DIESPAMDIEoptusnet.com.au> wrote: >> "Tim Little" <tim(a)little-possums.net> wrote in message >>> If you intend your proof to be "exactly the same as Cantor's, but with >>> the only difference being the word "computable" in front of the word >>> "Real"", it must start with a conditional introduction. In other >>> words, something like: >>> >>> "Suppose that L is a list of computable Reals. That is, L is a >>> function from N to R and for all n in N, there exists a Turing >>> Machine T_n such that when provided with k as input, T_n halts and >>> outputs the k'th decimal digit of L(n)." >> >> That's not how Cantor's proof starts. > > Correct: It didn't feature any mention of computable reals (but as I > recall it did feature the relevant properties of the definition of a > real number). > > I am presuming that you want *your* proof to substitute "computable > real" for "real", and therefore you need to substitute the definition > of computable real number for the definition of real number. That > means you also need to make that substitution in the definition of a > list of computable real numbers. > I can't see how the move from addition of "computable" in front of "Reals" requires any additional substitution in my "definition of a list". A list is simply a mapping from N. Yes, I want to know the first item, the second item etc; that is what a list is. > Are you starting to see now why it makes no sense to just drop > "computable" in front of every occurrence of the word "real" in the > proof? > Sort of. You are saying that you could effectively not specify what the first computable Real on the list is, because it depends upon some uncomputable function based on Chaitans. I can see why that is less of a problem to Cantor than it is to me, because he cares less about what it really was. But I still can't accept that you are providing a list of computable Reals when you aren't even telling me what the first one actually is. That's cheating. > > - Tim
From: WM on 20 Jun 2010 12:28 On 20 Jun., 17:51, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Cantor was this utterly insane freak who chose not to accept Newberry's > word for it, and instead *prove* that there was no list of all real > numbers. Obviously, his proof is nonsense, because, after all, Newberry > said there was no list. His proof is nonsense because it proves that a countable set, namely the set of all reals of a Cantor-list and all diagonal numbers to be constructed from it by a given rule an to be added to this list, cannot be listed, hence, that this indisputably countable set is uncountable. Even completely blinded matheologicians should be able, perhaps after some contemplation, to recognize that. Regards, WM
From: Mike Terry on 20 Jun 2010 13:33
"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. 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. > > > > > 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? :-) 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. 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. 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...) 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 proofs do not require computable lists, they work with just any old lists... > 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. 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. Surely you must be aware that this is NOT what computability means? Regards, Mike. |