halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: herbzet on 10 Aug 2008 01:32 julio(a)diegidio.name wrote: > herbzet 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. It's just a definition. That's what "limit point" means. Is that something different from "the limit entry"? > > 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), > elementary, and unambiguous meaning, just look at the construction. I think you need some sleep! ;) -- hz
From: julio on 10 Aug 2008 01:45 On 10 Aug, 06:32, herbzet <herb...(a)gmail.com> wrote: > It's just a definition. That's what "limit point" means. Is > that something different from "the limit entry"? Yes, is the answer still unclear? > > that has got a precise (I mean, in the limits of my possibilities), > > elementary, and unambiguous meaning, just look at the construction. > > I think you need some sleep! ;) What does that mean? Are you bored by getting answeres to request of clarifications? -LV > -- > hz
From: herbzet on 10 Aug 2008 01:54 julio(a)diegidio.name wrote: > 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. Ah, I get it. You were just saying that "The farther out we go in constructing the diagonal from the list, then [something]". It's just a way of speaking. You wrote: " 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." I still don't understand the conclusion, since I don't know what "the limit entry" means. Try me tomorrow. > The formal construction is based on the naturals and > (transf.) induction. Well, now you know what a limit point of a sequence is. Sometimes the diagonal number will be a limit point, sometimes not. -- hz
From: julio on 10 Aug 2008 02:08 On 10 Aug, 06:54, herbzet <herb...(a)gmail.com> wrote: > ju...(a)diegidio.name wrote: > > 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. > > Ah, I get it. You were just saying that "The farther out we go in > constructing the diagonal from the list, then [something]". It's > just a way of speaking. > > You wrote: > > " 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." > > I still don't understand the conclusion, since I don't know > what "the limit entry" means. No, I'd say it's the meaning of "induce" that you are missing. > Try me tomorrow. So it's you who need a sleep... ;) > > The formal construction is based on the naturals and > > (transf.) induction. > > Well, now you know what a limit point of a sequence is. Sometimes > the diagonal number will be a limit point, sometimes not. And, as I have told you, that notion of limit is just irrelevant to the diagonal argument. Anyway, have good dreams for now. -LV > -- > hz
From: David C. Ullrich on 10 Aug 2008 07:44
On Sat, 9 Aug 2008 18:42:50 -0700 (PDT), julio(a)diegidio.name wrote: >On 9 Aug, 23:30, Barb Knox <s...(a)sig.below> wrote: >> In article >> <7c07f984-0a79-4248-9078-6bf6c8398...(a)c58g2000hsc.googlegroups.com>, >> �ju...(a)diegidio.name wrote: >> > On 9 Aug, 07:20, Barb Knox <s...(a)sig.below> wrote: >> > > In article >> > > <371eb05c-831d-435d-8dea-966887ca4...(a)e39g2000hsf.googlegroups.com>, >> > > �ju...(a)diegidio.name wrote: >> > > > On 8 Aug, 19:00, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: >> [snip] >> > > > > Let me guess: You also think that an infinite set of numbers must >> > > > > contain an infinitely large number. >> >> > > > Easy guess. That number is called infinity, or otherwise "omega" ('w', >> > > > or even 'oo'). >> >> > > > With my construction I don't get higher order infinite ordinals, but >> > > > instead I get that 'oo' is representable, as is 'oo-1' and so on. That >> > > > is, we can enumerate from zero as well as enumerate back from >> > > > infinity. >> >> > > So then do you reject mathematical induction? >> >> > Absolutely not. I rather "double it". Informally speaking, I have two >> > end-points, zero and its mirror, infinity. Maybe keep in mind there is >> > no uncomputables in this realm. >> >> > > If not, then one can >> > > easily prove that oo < oo, which does not look healthy. >> >> > I'd be interested in seeing it, thanks. Mine is still mostly an >> > exploration. >> >> OK, I'll bite, since "exploration" does imply that you might under some >> circumstances reconsider your current position. > > >Very well appreciated. > > >> Here's a mathematical induction proof that oo < oo, using simple >> induction on N* (which is hereby defined as N augmented by the single >> limit point "oo"). >> >> Lemma: For all n in N*, n < oo. >> � Base case: clearly 0 < oo. >> � Induction step: Assume k < oo. �Then clearly k+1 < oo also. >> >> Applying the lemma to n = oo, we get oo < oo. >> QED. >> >> Thus mathematical induction does not work for N*. >> >> (Note: There is a form of induction that DOES work for "transfinite >> ordinals" -- see for example >> <http://en.wikipedia.org/wiki/Transfinite_induction>.) > > >Indeed, I have been using transfinite induction explicitly in my >recent posts on the argument. No, you haven't. You may think that's what you've been doing, but in fact you argument has been based on _exactly_ the sort of incorrect quasi-induction as in Barb's example. >Here I have dropped it, first because my >account was very fast and very informal, second because mentioning the >"transfinite" just led me reiterated accusations of being pompous with >no content and no understanding. Here's a hint: Any time you claim that you can show that R is countable or that there is an error in the standard proof of the uncountability of R people will conclude you have no understanding. Exactly as if you claimed to have a proof that 2 + 2 is not 4; then people would _correctly_ claim you didn't understand arithmetic. >So I thank you for bringing this up. > >Is now my argument safe? To be true: I think so, as I have in the >meantime discovered the "subcountables", so that I cannot be that off- >road after all... > >-LV > > >> -- >> --------------------------- >> | �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 � | � >> ------------------------------ David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.) |