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 9 Aug 2008 23:48 On 9 Aug 2008 04:50:50 -0700, stevendaryl3016(a)yahoo.com (Daryl McCullough) wrote: [...] Actually, Cantor himself did not consider /real numbers/ (and/or their decimal expansion) in his 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 a list of their decimal expansions), but a list of infinite sequences of the two symbols /a/ and /b/. Now 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. (See below.) With other words, it differs from every entry in the list. Slightly more formal approach: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Claim: If (l_i) is an infinite sequence such that its members l_i are infinite sequences of the symbols /a/ and /b/, then there is an infinite sequence d (of the symbols /a/ and /b/) such that d is not a member of (l_i) (i.e. for all n e N: d =/= l_n). Proof: Let [l_i]_j be the j-th members of the sequence l_i. We define a sequence d = (d_i) with: / /a/ if [l_i]_i = /b/ d_i = { \ /b/ if [l_i]_i = /a/ . Then for every natural number n: d =/= l_n, because for any natural number n, the n-th member of d differs from the n-th member of l_n. 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: julio on 10 Aug 2008 00:02 On 10 Aug, 04:48, Balthasar <nomail(a)invalid> wrote: > On 9 Aug 2008 04:50:50 -0700, stevendaryl3...(a)yahoo.com (Daryl > > McCullough) wrote: [...] > > Actually, Cantor himself did not consider /real numbers/ (and/or their > decimal expansion) in his 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 a list of their decimal expansions), but a list of > infinite sequences of the two symbols /a/ and /b/. Now 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. (See below.) With other words, it differs from every entry in > the list. That is Cantor thesis, and you just make it the usual non-sequitur. __It just does not hold as such for infinite sequences, unless one proves otherwise.__ > Slightly more formal approach: > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > Claim: If (l_i) is an infinite sequence such that its members l_i are > infinite sequences of the symbols /a/ and /b/, then there is an infinite > sequence d (of the symbols /a/ and /b/) such that d is not a member of > (l_i) (i.e. for all n e N: d =/= l_n). > > Proof: Let [l_i]_j be the j-th members of the sequence l_i. We define a > sequence d = (d_i) with: > > / /a/ if [l_i]_i = /b/ > d_i = { > \ /b/ if [l_i]_i = /a/ . > > Then for every natural number n: d =/= l_n, because for any natural > number n, the n-th member of d differs from the n-th member of l_n. Ditto: we are talking about infinite sequences, and that is at best a non sequitur... In fact, you keep "proving Cantor with Cantor". Over and over. -LV > 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: Ben Bacarisse on 10 Aug 2008 00:28 julio(a)diegidio.name writes: > On 9 Aug, 16:53, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: <snip> >> It would be best for me to say >> no more unless you define "computable real" and the ordering rule. > > > As I can see it, all ordering rules are equivalent modulo the > appropriate mapping. The "natural ordering" here I'd say is the usual > ordering for the permutations of the digits. With the period after the > diagonal element, just for reading purposes: > > 0:0(0) > 1:10(0) > 2:010(0) > 3:1100(0) > 4:00100(0) > ... > > Given, if I am not mistaken, that all ordering rules are equivalent > modulo mapping, interesting results follow, trivially. For instance, > the anti-diagonal here is simply the sequence: oo:(1). > > And we can enumerate backwards (again with the period after the > diagonal element): > > oo :1(1) > oo-1:01(1) > oo-2:101(1) > oo-3:0011(1) > oo-4:11011(1) > And, simmetrically, the "inverse" anti-diagonal we get is: 0:(0). Well I see what you are doing, but i don't see why you think it is interesting. You have a representation where every number can be written two ways (take the final 1 and replace with 01(1)). With such a representation the anti-diagonal can only be constructed if both representations are present. For example, if you alternate elements from your two lists the anti-diagonal is 0.101010101 = 2/3. It illustrates one of a vast family of rationals that are not on ether list: 1/3, 1/5, 1/6... Of course pi-3 is missing too, along with all the other transcendentals and irrationals in [0, 1]. Where does defining this countable subset of the rationals get you? -- Ben.
From: Ben Bacarisse on 10 Aug 2008 00:42 julio(a)diegidio.name writes: > On 10 Aug, 04:48, Balthasar <nomail(a)invalid> wrote: >> On 9 Aug 2008 04:50:50 -0700, stevendaryl3...(a)yahoo.com (Daryl >> >> McCullough) wrote: [...] >> >> Actually, Cantor himself did not consider /real numbers/ (and/or their >> decimal expansion) in his 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 a list of their decimal expansions), but a list of >> infinite sequences of the two symbols /a/ and /b/. Now 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. (See below.) With other words, it differs from every entry in >> the list. > > > That is Cantor thesis, and you just make it the usual non-sequitur. You can call it a thesis and claim it does not follow, but to make any headway you have to point out the flaw to all of us dumb sheep who find the proof convincing. Do you reject proof by contradiction? Do you reject idea of defining a sequence as a rule using data from all the elements of the list? Do you reject that the sequence so defined is in fact distinct? Something else? <snip> > In fact, you keep "proving Cantor with Cantor". Over and over. I have not see anyone make a proof that starts by assuming that the set is uncountable or even that uncountable sets exist. I certainly have not seen anything from you to explain the circularity you claim to see. -- Ben.
From: herbzet on 10 Aug 2008 00:38
julio(a)diegidio.name wrote: > herbzet wrote: > > ju...(a)diegidio.name 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. > > > > One problem here is that there may not be a unique limit point to > > the sequence enumerated by the list. > > Sorry, I don't get it. Could you be more specific? You say that the difference between the diagonal and "the limit entry" tends to zero. I'm saying that it's possible that "the limit entry" (whatever you mean by that) may not be unique: there may be more than one "limit entry". An infinite list of numbers from the interval [0, 1] will certainly have a /limit point/, as I mentioned at the end of my previous post. The problem is that for some lists (sequences) there is more than one /limit point/. > I also suppose this is the same objection as Balthasar's and Mr > McCullough's. Not quite. > But I don't know what you are hinting at here. I don't know what you mean by "the limit entry". I'm supposing that you might mean "the limit point". But a sequence (list) might have more than one limit point. A number L is a limit point of a sequence if for every interval [L + x, L - x] there is a member of the sequence (other than L) in that interval. In other words, a number L is a limit point of a sequence if there are numbers in the sequence arbitrarily close to L. Is this what what you mean by "the limit entry"? > > Example: Enumerate in some fashion the rational numbers in [0, 1]: > > > > q1, q2, q3, ... > > > > Then each rational qi is a limit point of the sequence, as is > > each irrational number in [0, 1]. (A Cantorian might remark > > that there are more limit points than entries in the list ...) > > I don't know what that means, for each qi to be a limit point of the > sequence. It means that every rational number q1, q2, q3, ... in [0, 1] has other rational numbers arbitrarily close to it. (It is also the case that any irrational number in [0, 1] has rational numbers arbitrarily close to it.) > > Certainly in this case the diagonal number will be a limit > > point of the sequence, though different from (unequal to) > > every member of the sequence. > > > > (It is of course a theorem of analysis that a bounded sequence > > of real numbers will have a limit point.) When you say the difference of the diagonal and the limit entry tends to zero, I ask, /which/ limit entry (if there's more than one)? -- hz |