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: stevendaryl3016 on 19 Jun 2010 08:12 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. >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. The set of computable reals is enumerable, but not recursively enumerable. The set of *all* reals is not enumerable. >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'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. >> 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. -- Daryl McCullough Ithaca, NY
From: stevendaryl3016 on 19 Jun 2010 08:42 Peter Webb says... > > >"Tim Little" <tim(a)little-possums.net> wrote in message >> The relevant point: the *only* input to the Turing machine in the >> definition is n. The rest of the tape must is blank. Peter >> apparently believes that a number is still computable even if the >> Turing machine must be supplied with an infinite amount of input (the >> list of reals). >> > >No. You said that you believed that if L is any list of computable reals, then antidiag(L) is computable. That's not true. It's only true if L is computable. Imagine that you have a Turing machine with two tapes: The first tape holds a list L of computable reals. The second tape holds a natural number, n. Then you can certainly program the Turing machine so that the output is the nth decimal place of the anti-diagonal of L. That doesn't mean that the antidiagonal is a computable real. For it to be a computable real, there has to be a Turing machine with only *one* input Tape, which contains a natural number, n. The Turing machine would have to output the nth decimal place of the antidiagonal *without* access to the original list L. In general, that's impossible. So there is a two-tape Turing machine that can compute the antidiagonal, but there is no one-tape Turing machine. So the antidiagonal is not computable, in general. >You seem to agree that the computable Reals are countable. Yes. >Do you agree that Cantor's diagonal proof when applied to a >purported list of all computable Reals will produce a computable Real >not on the list, No. It produces a *real* not on the list, not necessarily a computable real. Imagine a Turing machine tape T that contains a list of computable reals. There are various ways that a tape could contain a list of computable reals, but one way is this: The list contains a list of integers, each integer is a code for a Turing machine program for computing a real. Now, given the tape T above, you can write a Turing machine that computes the antidiagonal of T. But that *doesn't* mean that the antidiagonal is a computable real. For it to be computable, there has to be a Turing machine program that computes it *without* any auxiliary tapes such as T. Now, if T itself were computable, then the Turing machine could compute T, and then use T to compute the antidiagonal. But if T is not computable, then you can't compute the antidiagonal. -- Daryl McCullough Ithaca, NY
From: stevendaryl3016 on 19 Jun 2010 08:46 Peter Webb says... >Clearly there are countable sets that cannot be listed. > >Cantor proved that the Reals cannot be listed. His diagonal proof does *not* >show they are uncountable, any more than doing exactly the same proof with >computable Reals "proves" they are uncountable. That's completely wrong. Cantor's proof shows that there is no bijection between N and R, which by definition means that the reals are uncountable. It does *not* show that the computable reals are uncountable, because the antidiagonal is not necessarily a computable real. -- Daryl McCullough Ithaca, NY
From: stevendaryl3016 on 19 Jun 2010 09:06 Peter Webb says... >I agree that computable reals are countable. But I do not agree this means >they can be listed. In fact, I can easily prove they are not. If you give me >a purported list of all computable Reals I can use a diagonal argument to >form a computable Real not on the list. You can use a diagonal argument to form a *real* that is not on the list. For that real to be *computable*, you need to show that you can compute that real *without* using the list. If the list were a computable list, then you could reconstruct it yourself, so the antidiagonal would be computable. If the list is not computable, then neither is the antidiagonal. -- Daryl McCullough Ithaca, NY
From: Jesse F. Hughes on 19 Jun 2010 09:06
Newberry <newberryxy(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? Anyway, in a sense, you're right. If we assume that every real is represented by a sequence on the list, then we can prove that every sequence occurs on the list (ignoring the issue of multiple representations). And yet, we can also show that a particular sequence is not on the list. This is a contradiction and hence *our assumption* that every real is represented by a sequence on the list must be false. You've never seen proof by contradiction in your life? How remarkable. -- Jesse F. Hughes "Of course, I don't need any more education." -- Quincy P. Hughes (age 7) |