Why can no one in sci.math understand my simple point?
in [Logic]
|
From: |-|ercules on 19 Jun 2010 05:07 "Sylvia Else" <sylvia(a)not.here.invalid> wrote ... > On 19/06/2010 4:11 PM, |-|ercules wrote: > >> To support your argument you should at least show that you've formed a >> new sequence of digits. > > I'll explain it simply then. The first digit of the created number > differs from the first digit of the first number in the list. The second > digit differs from the second digit of the second number in the list. > > In general, digit n differs from digit n of the nth number in the list. > > So for all n, the created number differs from number n. Therefore the > created number is not in the list - it is a new sequence of digits. No I've told you all 20 times that does not create any new sequence at all. All you've done is CONSTRUCT a digit sequence like so An AD(n) =/= L(n,n) And then you say, it's different to each number like so PROOF An AD(n) =/= L(n,n) But you have not demonstrated a NEW SEQUENCE OF DIGITS. All you've done is this [ An AD(n) =/= L(n,n) -> An AD(n) =/= L(n,n) ] -> Superinfinity Your actual 'proof' is a specific example of the above 'proof'! [ An AD(n) = (L(n,n) + 1) mod 9 -> An AD(n) =/= L(n,n) ] -> Superinfinity Do you agree with the above version of Cantor's proof? > >> >> If you actually read my derivation of herc_cant_3 instead of blindly >> dismissing it, >> you'll see it holds, just like all digits of PI appear in order below >> this line, if interpreted >> correctly. >> >> Herc >> >> ___________________ >> >> 3 >> 31 >> 314 >> 3141 >> ... >> >> > > herc-cant-3 is not a derivation. It's a wild leap of faith. Nothing is > proved therein. > > Sylvia. Then which step do you disagree with? defn(herc_cant_3) The list of computable reals contains every digit (in order) of all possible infinite sequences. Derivation Given the increasing finite prefixes of pi 3 31 314 ... This list contains every digit (in order) of the infinite expansion of pi. Given the increasing finite prefixes of e 2 27 271 ... This list contains every digit (in order) of the infinite expansion of e. Given the increasing finite prefixes of ALL infinite expansions, that list contains every digit (in order) of every infinite expansion. So herc_cant_3 is true. The list of computable reals contains every digit (in order) of all possible infinite sequences. Herc -- "There are more things in Cantor's paradise, Horatio, than are dreamt of by your computers." ~ Barb Knox
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 |