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 11:33 On 9 Aug 2008 04:23:05 -0700, stevendaryl3016(a)yahoo.com (Daryl McCullough) wrote: >> >> Well, here I have to disagree. Actually, they do - in a certain sense. >> > I gave an example where the differences don't tend to zero. > Right. I guess it would be better to be more specific (for our crank) in this case: the "guaranteed differences" (i.e. the differences in the "worst case") tend to zero. > > It is *possible* for the differences to tend to zero, but > they [do not necessarily] tend to zero. > Right. 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 9 Aug 2008 11:53 Ben Bacarisse <ben.usenet(a)bsb.me.uk> writes: > julio(a)diegidio.name writes: > <snip> >> 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. And I mean we can enumerate forwards or backwards the >> infinite list of the computable reals, say in [0, 1], where 1 is the >> usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1. >> Actually, given an ordering rule over the list, we can enumerate >> forwards or backwards at some specific points, but I'll leave the >> details out. > > So order the list of "computable reals" in [0, 1] (I use quotes > because I am quoting you -- I don't know what these things are yet) to > get r1, r2, r3... and consider the list of numbers r(n): > > r1+(r2-r1)/2, r1+(r2-r1)/3, r1+(r2-r1)/4,... r1+(r2-r1)/(n+1),... > > All of these look computable to me so this list is simply a > permutation of r1, r2, r3... Which one is equal to r1 and which one > is equal to r2? What follows from r(x) = r1 and/or r(y) = r2? I now see that "permutation" is not correct. In fact, in trying to repair this argument, I now suspect that you define "computable" so you are actually enumerating the rationals in [0, 1] (or at least some other countable subset of the reals). It would be best for me to say no more unless you define "computable real" and the ordering rule. A reference would be fine. -- Ben.
From: herbzet on 9 Aug 2008 16:27 julio(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. 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 ...) 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.) -- hz
From: Barb Knox on 9 Aug 2008 18:30 In article <7c07f984-0a79-4248-9078-6bf6c8398841(a)c58g2000hsc.googlegroups.com>, julio(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. 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>.) -- --------------------------- | 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 | -----------------------------
From: julio on 9 Aug 2008 21:42
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. 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. 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 | > ------------------------------ |