halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: julio on 10 Aug 2008 01:01 On 10 Aug, 05:28, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > ju...(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. I don't know what taking such expansions as -- say -- 0.(9) and 1.(0) to be equal brings to this argument, and actually if it is pertinent at all. The point remains: the list is indeed and already _complete_. It is the infinite list of all the permutations of the digits in the infinite decimal expansion. > 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 No, you have just given another enumeration order, and again the list is complete and the anti-diagonal corresponds to the oo-th entry, etc. etc. Namely, in your example, 2/3, the anti-diagonal, is the oo-th entry. And we can again enumerate back. The list is still the same and complete: you have just changed the order. (The actual construction is maybe slightly subtler, in that for different enumeration rules (orders) and for each base of representation, there is a *class* (in the generic sense) of anti-diagonal sequences.) > : 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? It's meant to be the set of (all) the computable reals, surely a superset of the rationals. Actually a very significant set because of the importance of computability. -LV > -- > Ben.
From: herbzet on 10 Aug 2008 00:59 julio(a)diegidio.name wrote: > On 10 Aug, 02:47, ju...(a)diegidio.name wrote: > > On 9 Aug, 21:27, herbzet <herb...(a)gmail.com> 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? > > > > I also suppose this is the same objection as Balthasar's and Mr > > McCullough's. But I don't know what you are hinting at here. > > > > > 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. > > Hmm, maybe I get it. It's that I am a "post-cantorian > constructivist" ;) Right! ;) > That there are more reals than naturals is not a fact, but a > consequence of the "cantorian" line of reasoning via the diagonal > argument. That very argument is in question, then the rest is a > consequence, just as true as its premise. Sure. > Indeed, from the naturals and (transf.) induction only, I quite don't > get anything like that, and *that* is the toolset you are supposed to > start from. I'm just trying to figure out what you mean when you assert "the difference between the diagonal and the limit entry tends to zero". How do you know there's just one limit entry? The sequence (the list) may tend to many limit points. Example #2: 1/4, 3/8, 7/16, 15/32, ... This list of numbers tends to 1/2. 3/4, 7/8, 15/16, 31/32, ... This list of numbers tends to 1. I combine the two lists into one list: 1/4, 3/4, 3/8, 7/8, 7/16, 15/16, ... This list tends to both 1/2 and to 1. -- hz
From: julio on 10 Aug 2008 01:11 On 10 Aug, 05:38, herbzet <herb...(a)gmail.com> wrote: > ju...(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. That is my point. You are talking "analysis", but that's way beyond the diagonal argument. Here you have sequences of naturals and induction, that's it. > 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)? The answer: "limit" there is informal. The formal definition and the construction is by (transf.) induction over the naturals. In that context, I say the "limit" sequence to mean the "oo-th" sequence and equivalent labels. That sequence, the limit or oo-th sequence, not only exists in general, by transf. induction over the (extended) naturals, but we can even actually from it. That is, formally, all that has got a precise (I mean, in the limits of my possibilities), elementar, and unambiguous meaning, just look at the construction. -LV > -- > hz
From: julio on 10 Aug 2008 01:17 On 10 Aug, 05:42, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > ju...(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. You might be confused between my objections to Balthasar and my objections to Cantor's argument. This one is simply what it is, a non-sequitur. > 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. And the one below too: > 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. Of course it's proven by Cantor. The culprit is on the free usage of "all/any". That's not Cantor's fault. -LV > -- > Ben.
From: julio on 10 Aug 2008 01:35
On 10 Aug, 05:59, herbzet <herb...(a)gmail.com> wrote: > ju...(a)diegidio.name wrote: > > On 10 Aug, 02:47, ju...(a)diegidio.name wrote: > > > On 9 Aug, 21:27, herbzet <herb...(a)gmail.com> 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? > > > > I also suppose this is the same objection as Balthasar's and Mr > > > McCullough's. But I don't know what you are hinting at here. > > > > > 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. > > > Hmm, maybe I get it. It's that I am a "post-cantorian > > constructivist" ;) > > Right! ;) > > > That there are more reals than naturals is not a fact, but a > > consequence of the "cantorian" line of reasoning via the diagonal > > argument. That very argument is in question, then the rest is a > > consequence, just as true as its premise. > > Sure. > > > Indeed, from the naturals and (transf.) induction only, I quite don't > > get anything like that, and *that* is the toolset you are supposed to > > start from. > > I'm just trying to figure out what you mean when you assert "the > difference between the diagonal and the limit entry tends to zero". > > How do you know there's just one limit entry? > > The sequence (the list) may tend to many limit points. > > Example #2: > > 1/4, 3/8, 7/16, 15/32, ... > > This list of numbers tends to 1/2. > > 3/4, 7/8, 15/16, 31/32, ... > > This list of numbers tends to 1. > > I combine the two lists into one list: > > 1/4, 3/4, 3/8, 7/8, 7/16, 15/16, ... > > This list tends to both 1/2 and to 1. No no, no limits of ratios and similar stuff involved. I were just hinting at the common notion of n->oo over a sequence. That is the kind of "limit" I was hinting at, and, again, talking about such limit and the limit of a difference was informal and mostly analogical. The formal construction is based on the naturals and (transf.) induction. -LV > -- > hz |