halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Daryl McCullough on 8 Aug 2008 19:06 julio(a)diegidio.name says... >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. That's completely false. Let's try an example: Suppose your list is the following: 0.[1]000000.... 0.0[1]00000.... 0.00[1]0000... 0.000[1]000... etc. (Note, I put a [] around each digit of the diagonal) Now, to diagonalize, we add 1 to each diagonal element. This gives the number 0.22222... That number does not appear on the list, and it is certainly not equal to the limit of the numbers on the sequence. When someone says "The diagonal differs from the 2nd entry in the 2nd place" they don't mean that that is the *only* place they differ. The diagonal may differ from the 2nd entry in many places, but it differs in at least the 2nd place. So, no, your simple argument doesn't show the opposite result. -- Daryl McCullough Ithaca, NY
From: julio on 8 Aug 2008 19:09 On 8 Aug, 23:41, MoeBlee <jazzm...(a)hotmail.com> wrote: > On Aug 8, 3:09 pm, ju...(a)diegidio.name wrote: > > On 8 Aug, 19:10, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > On Aug 8, 10:23 am, ju...(a)diegidio.name wrote: > > > > Otherwise, you are free to mention EXACTLY what premises in the > > > proof or what rule of logic used you disagree with. > > > The diagonal argument is broken in its essence, and this comes before > > your axioms, another problem of yours. > > You see. You didn't answer the question. You won't say what axioms or > rules you disagree with. Okay, fine, so we just leave it at that. > Since the axioms and rules entail a conclusion you disagree with, > there is at least one, though unspecified axiom or rule, that you > don't accept. Reread: you see? You just don't get it, it's out of your universe of understanding. BTW, now you have made a point of denying anything I might be willing to say, here and elsewhere. I have already given you a formal definition of my construction in a another thread, along with any of the uncountable and meanigless clarifications I was asked for, about all the details you liked to be told about. Result: just reitereted denial and personal insults. Balthasar is now your friend. And I am finished with you both. -LV
From: Daryl McCullough on 8 Aug 2008 19:09 julio(a)diegidio.name says... >There is no reason for your "moreover". Moreover, the difference in >question tends to zero, so that the anti-diagonal happens to >correspond to the limit entry: you have (yet) not addressed that. No, the anti-diagonal does *not* equal the "limit entry". Why would you think that? The differences *don't* tend to zero. Look at an actual example: 0.10000... 0.01000... 0.001000... 0.0001000... etc. The anti-diagonal is 0.2222... That doesn't appear on the list, and it also isn't equal to the limit of the list. -- Daryl McCullough Ithaca, NY
From: julio on 8 Aug 2008 19:14 On 9 Aug, 00:06, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > ju...(a)diegidio.name says... > > >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. > > That's completely false. Let's try an example: Suppose > your list is the following: > > 0.[1]000000.... > 0.0[1]00000.... > 0.00[1]0000... > 0.000[1]000... > > etc. (Note, I put a [] around each digit of the diagonal) > > Now, to diagonalize, we add 1 to each diagonal element. This > gives the number > > 0.22222... > > That number does not appear on the list, and it is certainly > not equal to the limit of the numbers on the sequence. > > When someone says "The diagonal differs from the 2nd entry in the > 2nd place" they don't mean that that is the *only* place they > differ. The diagonal may differ from the 2nd entry in many places, > but it differs in at least the 2nd place. > > So, no, your simple argument doesn't show the opposite result. Good one, at least looks like mathematics. Although your construction is rather itself "broken": not less good for my argument then it might be for Cantor's. Shall I point you to some article on the diagonal argument? For the sake of the discussion. -LV > -- > Daryl McCullough > Ithaca, NY
From: Balthasar on 8 Aug 2008 19:16
On Fri, 8 Aug 2008 15:49:27 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> wrote: > > P.S. It is decidedly NOT constructivist to assert the existence of a > "limit" without CONSTRUCTING it (and just saying "the limit case" is > decidedly not a construction), let alone, not even defining what > possible sense you might mean by a "limit" in such a context. > And, btw., even a constructivist/intuitionist would agree that a number is not in a certain set (or list) if it differs from ALL (i.e. each and every) elements (or entries) in the set (or list). ;-) Proof (in NJ + identity): 1 (1) Ax(x e A -> ~(a = x)) A 2 (2) a e A A 1 (3) a e A -> ~(a = a) 1 UE 1,2 (4) ~(a = a) 2,3 ->E (5) a = a =I 1,2 (6) _|_ 4,5 ~E 1 (7) ~(a e A) 2,6 ~I Hence: Ax(x e A -> a =/= x) |- a !e A. This does even hold in ML (minimal logic) + identity. But obviously id does not hold in /crank logic/. 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) |