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 11 Aug 2008 04:26 On Sun, 10 Aug 2008 08:24:40 -0700 (PDT), julio(a)diegidio.name wrote: >On 10 Aug, 15:54, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: >> ju...(a)diegidio.name writes: >> > How do you dismiss constructive theories? I'd be very interested in >> > learning what eventually there is to lose. >> >> Sadly, the diagonal argument is constructively valid. You will need >> look elsewhere for vindication. > >I'll get it when someone points out the flaw in _my_ argument. Maybe you didn't notice, but many people have pointed out many flaws. You've never given a version where the notation and the exposition was coherent, and when a person tries to read between the lines to figure out what you mean he finds a very common error (common on sci.math and sci.logic): your proof actually shows that the set of _finite_ subsets of N is countable, which is a true fact but no news. The problem is that the power set of N is simply not the limit as n tends to infinity of the power set of {1,...,n}. >I know that Cantor's result is usually accepted even in the >constructive domain (though I wouldn't say it is "constructively >valid" tout court). That's why I have said "post-cantorian" along with >"constructivist". These "post-cantorians" only exist in your imagination. >BTW, and in case you really wander: I am looking for no vindication. >All that fuzz seems rather the official rule of the house - so to say. >As a matter of fact, I am learning my mathematical language here in >the groups. What you _seem_ to be learning is two techniques, which work very well together: (i) simply ignore careful explanations of your errors (ii) complain that there's no explanation given in posts that don't repeat the explanations. >-LV > >> -- >> Aatu Koskensilta (aatu.koskensi...(a)uta.fi) >> >> "Wovon man nicht sprechen kann, dar�ber muss man schweigen" >> �- Ludwig Wittgenstein, Tractatus Logico-Philosophicus 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: herbzet on 11 Aug 2008 04:28 julio(a)diegidio.name wrote: > herbzet wrote: > > 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. That may be so; but I definitely don't know what the proposition we are to induce means because I don't know what "the limit entry" means. We've established that it doesn't mean "the limit point". You may feel you've already sufficiently defined the term, but would you be good enough to state it here once again? Maybe I'll get it this time. > > 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. Agreed! -- hz
From: julio on 11 Aug 2008 05:32 On 11 Aug, 09:28, herbzet <herb...(a)gmail.com> wrote: > ju...(a)diegidio.name wrote: > > herbzet wrote: > > > 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. > > That may be so; but I definitely don't know what the proposition > we are to induce means because I don't know what "the limit entry" > means. We've established that it doesn't mean "the limit point". > You may feel you've already sufficiently defined the term, but > would you be good enough to state it here once again? Maybe > I'll get it this time. You should just make up your mind. Are you after an informal presentation or a formal one. I have given both and it seems to me you just need to focus on the distinction and avoid the mix. > > > 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. > > Agreed! Glad about it, another unsurmountable gate is now open. ;) -LV > -- > hz
From: julio on 11 Aug 2008 05:40 On 11 Aug, 09:26, David C. Ullrich <dullr...(a)sprynet.com> wrote: > On Sun, 10 Aug 2008 08:24:40 -0700 (PDT), ju...(a)diegidio.name wrote: > >I'll get it when someone points out the flaw in _my_ argument. > > Maybe you didn't notice, but many people have pointed > out many flaws. Not only I noticed, I have exactly noticed who has been saying what. > These "post-cantorians" only exist in your imagination. That's just your permanent war, get lost with it. > What you _seem_ to be learning is two techniques, which > work very well together: (i) simply ignore careful explanations > of your errors (ii) complain that there's no explanation given > in posts that don't repeat the explanations. That you are intellectually dishonesty and void I have learnt. -LV
From: julio on 11 Aug 2008 05:53
On 10 Aug, 17:46, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > ju...(a)diegidio.name writes: > > On 10 Aug, 05:42, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > >> ju...(a)diegidio.name writes: > >> <snip> > > >> > In fact, you keep "proving Cantor with Cantor". Over and over. > > >> I have not see anyone make a proof that starts by assuming that the > >> set is uncountable or even that uncountable sets exist. I certainly > >> have not seen anything from you to explain the circularity you claim > >> to see. > > > You might be confused between my objections to Balthasar and my > > objections to Cantor's argument. > > I may well be. I was hoping you'd address the questions I asked > seeking clarification. But you have not clarified if you are after my objections to Blathasar and co. or to Cantor's argument. The circularity and misunderstanding is in Blathasar and co's, the problem with Cantor is much more subtle. > Something, somewhere, in that chain of > reasoning leading to the cardinality of the power set is something > that you do not accept. An upper bound for the cardinality of the powerset is just a side result of my construction. The "reasoning" here should be on the construction itself, there is no point in warrying for the side result -- for how interesting and dramatic it could be -- until the construction has been understood and validated. > Suggesting that the argument is circular > means I should be looking for the conclusion as one of the premises, > but I don't see it there. There where? You have not clarified. > > This one is simply what it is, a non-sequitur. > > >> Now this sequence differs from any sequence in the list by at least one > >> symbol. (See below.) With other words, it differs from every entry in > >> the list. > > [BTW, I did not write this (nor the quote below) as I did the other > texts with the same number of quote indentations. When you add text > from a third source, I think it helps to mark it with some new quote > character. I use |.] > > > And the one below too: > > >> Then for every natural number n: d =/= l_n, because for any natural > >> number n, the n-th member of d differs from the n-th member of l_n. > > > Of course it's proven by Cantor. The culprit is on the free usage of > > "all/any". > > I don't see the problem, but equally I don't see the point in batting > this back and forth in a plain text medium. If you have an alternate > axiom set you prefer So you too now after an axiomatization? The naturals plus transfinite induction is the asnwer I have repeatedly given. First, should be easy enough for you to get what that entails, second, about this crux of the axioms, there is some interesting comments going on in other threads. -LV > maybe you could just point me at it? If you have > a favourite paper or book with a formal exposition of Cantor's result > to which you can say: "line 523 is the one that does not follow" then > we can take is further. Otherwise, you'll just be saying you find > some informal argument unacceptable where to me it seems fine. A more > formal notation is the only way forward. > > -- > Ben. |