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 22:30 On Fri, 8 Aug 2008 18:00:35 +0000 (UTC), Chris Menzel <cmenzel(a)remove-this.tamu.edu> 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. >>>>> >>>>> (Crank) >>>>> >>>> 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. >>>> One might also ask what "limit entry" are you talking about - limit of what sequence? >>>> >>>> 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. >>>> >>>> (MoeBlee) >>>> >>> To make a long story short: we are not interested in the "limit >>> entry" (whatever that may be), but in the fact that the [anti-] >>> diagonal differs from each and any entry in the list. >>> >>> (Balthasar) >>> >> 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 >> >> (Crank) >> > Let me guess: You also think that an infinite set of [natural] numbers > must contain an infinitely large number. > > (Chris Menzel) > Certainly an educated guess. :-) 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 9 Aug 2008 02:12 On 8 Aug, 19:00, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: > On Fri, 8 Aug 2008 10:23:21 -0700 (PDT), ju...(a)diegidio.name > <ju...(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. 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. 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. Side result is again that the list of the computable reals is in bijection with the set of the naturals. And, given that its numerosity is in the order of n! (all the permutations of the digits) we have an upper bound for the powerset, whose numerosity is in the order of 2^n. -LV
From: Barb Knox on 9 Aug 2008 02:20 In article <371eb05c-831d-435d-8dea-966887ca4463(a)e39g2000hsf.googlegroups.com>, julio(a)diegidio.name wrote: > On 8 Aug, 19:00, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: > > On Fri, 8 Aug 2008 10:23:21 -0700 (PDT), ju...(a)diegidio.name > > <ju...(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. > > 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? If not, then one can easily prove that oo < oo, which does not look healthy. (And there are many other similar difficulties with attempting to add a limit point to N.) [snip] -- --------------------------- | 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: Balthasar on 9 Aug 2008 02:28 On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> wrote: > > Moreover, the anti-diagonal differs from every entry in the list. > That's all that is required to show that the anti-diagonal is not > on [or in] the list. > In the following I'll give a formal proof for this (the latter) claim. First some definitions. The /list/ L will be represented as an infinite sequence: L = (l_n). The l_ns are the /entries/ in the list L = (l_n). Accordingly we define for any list L = (l_n): x in L =df En(n e N & x = l_n). "x is in the list L." x not in L =df ~(x in L) "x is not in the list L." Now we have the assumption: L = (l_n) & An(n e N -> ~(d = l_n)). "The anti-diagonal d differs from every entry in the list L." We want to prove: d not in L. "The anti-diagonal d is not in the list L." Proof (in NJ + identity): 1 (1) L = (l_n) & An(n e N -> ~(d = l_n)) A 2 (2) d in L A 1 (3) L = (l_n) 1 &E 1,2 (4) d in (l_n) 2,3 =E 1,2 (5) En(n e N & d = l_n) 4 Def. "in" 6 (6) a e N & d = l_a A 6 (7) a e N 6 &E 6 (8) d = l_a 6 &E 1 (9) An(n e N -> ~(d = l_n)) 1 &E 1 (10) a e N -> ~(d = l_a) 9 UE 1,6 (11) ~(d = l_a) 7,10 ->E 1,6 (12) _|_ 8,11 ~E 1,2 (13) _|_ 5,6,12 EE 1 (14) ~(d in L) 2,13 ~I 1 (15) d not in L 14 Def. "not in" Hence we have shown: L = (l_n) & An(n e N -> ~(d = l_n)) |- d not in L. qed. The proof will even go trough in minimal logic + identity. Though it will fail in some systems of /crank logic/: "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) B.
From: julio on 9 Aug 2008 02:29
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: > > > On Fri, 8 Aug 2008 10:23:21 -0700 (PDT), ju...(a)diegidio.name > > > <ju...(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. > > > 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. -LV > (And there are many other similar difficulties with attempting to add a > limit point to N.) > > [snip] > -- > --------------------------- > | 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 | > ------------------------------ |