halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: David C. Ullrich on 9 Aug 2008 05:37 On Fri, 8 Aug 2008 16:14:34 -0700 (PDT), julio(a)diegidio.name wrote: >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. Huh? His "argument" is simply a carefully written example of what might be happening in that diagonal argument. It shows explicitly why what you said makes no sense, as everyone's been saying. (You could have saved youself the trouble of embarassing yourself again by coming up with "his argument" yourself, by the way - all he did was go through the proof with an explicit example of a list of reals.) It's just an illustration of what's going on in the proof. How in the world is this "not less good" for the proof? >Shall I point you to some article on the diagonal argument? For the >sake of the discussion. > >-LV > > >> -- >> Daryl McCullough >> Ithaca, NY 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.)
From: julio on 9 Aug 2008 06:05 On 9 Aug, 10:37, David C. Ullrich <dullr...(a)sprynet.com> wrote: > On Fri, 8 Aug 2008 16:14:34 -0700 (PDT), ju...(a)diegidio.name wrote: > >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. > > Huh? His "argument" is simply a carefully written example > of what might be happening in that diagonal argument. If that's a carefully written example of what might be happening in that diagonal argument, hmm... yes, I guess that's what I meant. Shall I point you too to some article on the diagonal argument? -LV > It shows explicitly why what you said makes no sense, > as everyone's been saying. (You could have saved youself > the trouble of embarassing yourself again by coming > up with "his argument" yourself, by the way - all he did > was go through the proof with an explicit example of > a list of reals.) > > It's just an illustration of what's going on in the proof. > How in the world is this "not less good" for the proof? > > >Shall I point you to some article on the diagonal argument? For the > >sake of the discussion. > > >-LV > > >> -- > >> Daryl McCullough > >> Ithaca, NY > > 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.)
From: Daryl McCullough on 9 Aug 2008 07:23 Balthasar says... > >On 8 Aug 2008 16:09:48 -0700, stevendaryl3016(a)yahoo.com (Daryl >McCullough) wrote: > >> >> No, the anti-diagonal does *not* equal the "limit entry". >> >It doesn't? So YOU know how the /limit entry/ is defined? Well, at least >*I* don't know how it is defined, hence *I* can't claim that - since I >don't have a proof for this assertion. [...] > >> >> Why would you think that? >> >Because he's a troll or a crank? > >> >> The differences *don't* tend to zero. >> >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. It is *possible* for the differences to tend to zero, but they are not guaranteed to tend to zero. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 9 Aug 2008 07:50 julio(a)diegidio.name says... > >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": No, I showed that *your* argument was broken. You said something nonsensical and you gave a false proof of it. >Shall I point you to some article on the diagonal argument? Shall I point you to some article on what a logical argument is? >For the sake of the discussion. If someone tried to have a discussion with you about whether 2 is an odd number, or whether the square-root of 10 is an integer, what do you think would come out of that discussion? Just take the following: Claim: If f(i) is a function that takes a natural number i and returns a real number between 0 and 1, then there is a real number r between 0 and 1 such that f(i) is never equal to r. Proof: Let f(i)[j] be decimal place number j of f(i). We construct a new real r whose jth decimal place r[j] is given by: If f(i)[i] > 4, then r[i] = f(i)[i] + 1. Otherwise, r[i] = f(i)[i] - 1. (This guarantees that r[i] is 1,2,3,4,5,6,7, or 8, avoiding the cases of decimals that end with all 0s or all 9s) Then for every natural number i, r is unequal to f(i), because the ith decimal place of r is 1 different from the ith decimal place of f(i). -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 9 Aug 2008 07:59
In article <890f3e63-813c-4844-8c06-a8ae5c1a3b8f(a)k7g2000hsd.googlegroups.com>, julio(a)diegidio.name says... > >On 9 Aug, 00:16, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: >> ju...(a)diegidio.name says... >> >> >So you cannot add anything significant, you just reiterate your >> >insults to my intelligence. Never mind, it was anyway very >> >"instructive". >> >> Look, Cantor made a precise claim, and he gave a rigorous proof >> of that claim. You made a fuzzy claim (one that didn't actually >> contradict what Cantor said), and you gave a false proof of that >> fuzzy claim. I guess it's not nice to insult your intelligence, >> but you clearly don't know what you are talking about. > > >And you clearly can only reiterate you spell. Yes, these newsgroup consists mostly of reiterations of the following process: 1. A crank claims to prove that some well-known theorem is false. 2. Multiple non-cranks explain how he is mistaken. The cycle can't really end, because the crank is either not willing or not able to understand the explanations, and the non-cranks are either not willing or not able to just let someone wallow in his own ignorance. Every conceivable argument against Cantor's theorem has already been trotted out, many times before. So yes, it's all reiteration, including what you are saying and what people are saying in response to you. Only the players change... -- Daryl McCullough Ithaca, NY |