halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Balthasar on 8 Aug 2008 19:48 On Fri, 8 Aug 2008 16:42:21 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> wrote: >> >> You lose, badly now. >> Drunk, drugs? >> >> And I am officially the new "king of the post-cantorians", by your own >> appointment. >> >> Cooool. >> > Sweet indeed. > Yeah, very cool, indeed! :-) B. -- "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." (WM, sci.logic)
From: Balthasar on 8 Aug 2008 20:04 On Sat, 09 Aug 2008 01:35:54 +0200, Balthasar <nomail(a)invalid> wrote: >> >> The differences *don't* tend to zero. >> > Well, here I have to disagree. [etc.] > Well, actually Cantor himself did not consider /real numbers/ (and/or their decimal expansion) in the original proof (where he introduced the diagonal argument), hence all this (cranky) talking about "limits" and "limit entry" and whatnot could not arise. B. -- "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." (WM, sci.logic)
From: Balthasar on 8 Aug 2008 20:48 On Sat, 09 Aug 2008 02:04:52 +0200, Balthasar <nomail(a)invalid> wrote: >>> >>> The differences *don't* tend to zero. >>> >> Well, here I have to disagree. [etc.] >> > Well, actually Cantor himself did not consider /real numbers/ (and/or > their decimal expansion) in the original proof (where he introduced the > diagonal argument), hence all this (cranky) talking about "limits" and > "limit entry" and whatnot could not arise. > So, for the sake of the argument, let's not consider a list of real numbers (and/or of their decimal expansions), but a list of infinite sequences of the two symbols /a/ and /b/. Let's just consider one such list (to point out the construction of the anti-diagonal): (1) [a] a b b a a b a ... (2) a [a] a a a a b b ... (3) b b [b] b a a b a ... (4) a b b [b] a b b b ... : ... (Note, I put a [] around each symbol of the diagonal.) In this case we get the anti-diagonal by replacing /a/ with /b/ and vice versa. Hence we get the sequence b b a a ... Now this sequence differs from any sequence in the list by at least one symbol. (Exercise!) With other words, it differs from each and any sequence in the list, i.e. it's not in the list (at least following standard logic). B. -- "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." (WM, sci.logic)
From: Chris Menzel on 8 Aug 2008 14:00 On Fri, 8 Aug 2008 10:23:21 -0700 (PDT), julio(a)diegidio.name <julio(a)diegidio.name> said: > On 8 Aug, 18:12, Balthasar <nomail(a)invalid> wrote: >> On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee >> <jazzm...(a)hotmail.com> wrote: >> >> >> Below again a simple argument to show that from the very same >> >> construction we could induce the exact opposite result: >> >> >> 1: The diagonal differs from the 1st entry in the 1st place; 2: >> >> The diagonal differs from the 2nd entry in the 2nd place; ... n: >> >> The diagonal differs from the n-th entry in the n-th place; >> >> >> It seems straightforward to induce that, at the limit, the >> >> difference between the diagonal and the limit entry tends to zero. >> >> > WHAT limit? You need to DEFINE "limit" in terms of some topology, >> > metric, ordering, or whatever. We don't just use the word "limit" >> > without the context of the EXACT sense of a limit as it has been >> > DEFINED. >> >> > Moreover, the anti-diagonal differes from every entry in the list. >> > That's all that is required to show that the anti-diagonal is not >> > on the list. >> >> To make a long story short: we are not interested in the "limit >> entry" (whatever that may be), but in the fact that the diagonal >> differs from each and any entry in the list. > > Interested or not, you cannot just dismiss it. The "limit" entry makes > just as much sense as the above (or the below) "[for] every entry in > the list". Is the list "infinite" or is it not? I am saying, yours is Let me guess: You also think that an infinite set of numbers must contain an infinitely large number.
From: Barb Knox on 8 Aug 2008 22:16
In article <slrng9p2e3.af4.cmenzel(a)philebus.tamu.edu>, Chris Menzel <cmenzel(a)remove-this.tamu.edu> wrote: > On Fri, 8 Aug 2008 10:23:21 -0700 (PDT), julio(a)diegidio.name > <julio(a)diegidio.name> said: > > On 8 Aug, 18:12, Balthasar <nomail(a)invalid> wrote: > >> On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee > >> <jazzm...(a)hotmail.com> wrote: > >> > >> >> Below again a simple argument to show that from the very same > >> >> construction we could induce the exact opposite result: > >> > >> >> 1: The diagonal differs from the 1st entry in the 1st place; 2: > >> >> The diagonal differs from the 2nd entry in the 2nd place; ... n: > >> >> The diagonal differs from the n-th entry in the n-th place; > >> > >> >> It seems straightforward to induce that, at the limit, the > >> >> difference between the diagonal and the limit entry tends to zero. > >> > >> > WHAT limit? You need to DEFINE "limit" in terms of some topology, > >> > metric, ordering, or whatever. We don't just use the word "limit" > >> > without the context of the EXACT sense of a limit as it has been > >> > DEFINED. > >> > >> > Moreover, the anti-diagonal differes from every entry in the list. > >> > That's all that is required to show that the anti-diagonal is not > >> > on the list. > >> > >> To make a long story short: we are not interested in the "limit > >> entry" (whatever that may be), but in the fact that the diagonal > >> differs from each and any entry in the list. > > > > Interested or not, you cannot just dismiss it. The "limit" entry makes > > just as much sense as the above (or the below) "[for] every entry in > > the list". Is the list "infinite" or is it not? I am saying, yours is > > Let me guess: You also think that an infinite set of numbers must > contain an infinitely large number. That's a good bet. I guess it's time to repost this: I am the very model of a modern non-Cantorian, With insights mathematical as good as any saurian. I rattle the Establishment's foundations with prodigious ease, And populate the counting numbers with some new infinities. I've never studied axioms of sets all theoretical, But that's just ted'ous detail, whereas MY thoughts are heretical And cause the so-called experts rather quickly to exasperate, While I sit back and mentally continue just to .... -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | ----------------------------- |