halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: julio on 11 Aug 2008 06:03 On 10 Aug, 18:46, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > Balthasar <nomail(a)invalid> writes: > > Actually, a slightly more formal approach has already been > > delivered: > > Yes, I has seen you sterling work trying to pin the problem down, but > because of what followed, I though it had become a dead end... He won't get it. Now he's opening personal threads to tell it better. > > So it seems he must object against extensionality too: > > I am at a loss to know what is missing but I have a suspicion from > another sub-thread. The binary digits example he posted has a > problem: the conventional anti-diagonal construction (by symbol > manipulation only) yields a string with value already on the list > (because values on the list have duplicate representations as finite > binary strings). I suspect he has been thrown by this apparently > miraculous "hole" in the conventional construction. I frankly don't know which hole you are refering to in the conventional construction. I have the slight feeling that you may still be a bit confused as to what's in "my" list, because your remarks do not apply. The list, as I have defined it, is just "complete": it is the list of all the permutations of the digits over the infinite decimal expansion. There is no "duplicates": duplicates come out from a further definition about some equalities, defiition and equalities that are absolutely irrelevant here (someone has pointed out, although of course attributing the error to me, that we are manipulating symbols, not really "numbers"). The list is complete of all the possible decimal expansions: that is, it is the list off all the _computable reals_, includind the rationals and all computable irrationals. Then, that there is more than that, it is Cantor's. -LV
From: herbzet on 11 Aug 2008 06:44 julio(a)diegidio.name wrote: > 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. Well, a reasonably rigorous informal presentation would probably be OK -- we could work out any formal kinks as we go along. > I have given both and it seems to me you > just need to focus on the distinction and avoid the mix. Yes, I have read your replies to others and I'm pretty confused. It occurs to me now that "the limit entry" might be referring to the diagonal ("the limit entry of the diagonal") rather than, as I supposed, the list ("the limit entry of the list"). Such is the degree of my confusion. I invite you to re-state your definition of "the limit entry" so I'll understand what the conclusion of your above argument is asserting. I'm not asking you to prove anything -- just to define a term. Thanx for your trouble. -- hz
From: julio on 11 Aug 2008 07:07 On 11 Aug, 11:44, herbzet <herb...(a)gmail.com> wrote: > Such is the degree of my confusion. And you keep insisting with your confusion while disregarding my explanations. How will we get out of such empasse? The "limit entry" is indeed the "last" entry in the _list_, that is, the oo-th entry. This I have stated over and over and over. Then there is the formal definition and construction, which you have up to here ignored, although that that should be the reference point for any serious debate, that too I have repeated over and over and over. Ignored from you up to now. Why should I rewrite it again, which would be maybe the 10-th time in less than a week? Will you eventually just "read"? -LV
From: julio on 11 Aug 2008 09:40 On 10 Aug, 17:46, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > A more formal notation is the only way forward. I thank you for the feedback. I will post something more proper when I am able, the quest is surely not over. BTW, I have been, mistakenly although informally, saying "permutations". I now realize how misleading that must have been. I apologise for the overall confusion. -LV > -- > Ben.
From: herbzet on 11 Aug 2008 09:36
julio(a)diegidio.name wrote: > herbzet wrote: > > > Such is the degree of my confusion. > > And you keep insisting with your confusion while disregarding my > explanations. How will we get out of such empasse? Well, I'm not that bright. > The "limit entry" is indeed the "last" entry in the _list_, that is, > the oo-th entry. This I have stated over and over and over. OK, it's the oo-th entry of the list. That wasn't so hard to say, was it? > Then there is the formal definition and construction, which you have > up to here ignored, although that that should be the reference point > for any serious debate, that too I have repeated over and over and > over. Ignored from you up to now. Well, I wasn't sure that you didn't mean "the limit point of the list" which was my best guess at what you meant (though Daryl beat me to making this interpretation). Now that I know that the limit entry is the oo-th entry of the list, I'll look again at your previous posts to other people to find out exactly what the oo-th entry is. I must say though, that I doubt that I'm going to find that the difference between the diagonal of a list and the oo-th entry of the list tends to zero, not least because we can construct different diagonal numbers off the same list. Will they all tend to the oo-th entry? > Why should I rewrite it again, which would be maybe the 10-th time in > less than a week? Will you eventually just "read"? Well, I'll give it a try. Stand by. -- hz |