Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | sci.logic, comp.theory |
| Subject | Re: Necessary sequence of halt decider's inference chain |
| Date | 2018-02-13 17:13 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87vaf0g6e7.fsf@bsb.me.uk> (permalink) |
| References | (8 earlier) <JdCdna8MAbPHeeLHnZ2dnUU7-aXNnZ2d@giganews.com> <874lmnjyhc.fsf@bsb.me.uk> <eYydnSl6VsUH0x_HnZ2dnUU7-YHNnZ2d@giganews.com> <87po59h69h.fsf@bsb.me.uk> <fqqdnTjeI4zwkR7HnZ2dnUU7-UvNnZ2d@giganews.com> |
Cross-posted to 2 groups.
Pete Olcott <Pete@NoEmail.address> writes: > On 2/12/2018 10:18 PM, Ben Bacarisse wrote: >> Pete Olcott <Pete@NoEmail.address> writes: >> >>> On 2/11/2018 10:13 AM, Ben Bacarisse wrote: >>>> I had lots of comments but then got to the part where we agree. It >>>> seemed silly to reply to all the details before that. The agreement >>>> seems significant so I cut the rest to concentrate on this bit: >>>> >>>> Pete Olcott <Pete@NoEmail.address> writes: >>>>> On 2/10/2018 11:06 AM, Ben Bacarisse wrote: >>>>>> Pete Olcott <Pete@NoEmail.address> writes: >>>> <snip> >>>>>>> In the case of halt deciders >>>>>>> evaluating finite strings defined within the language or Turing Machine >>>>>>> Descriptions this chain of inference must necessarily involve every >>>>>>> single state transition of the TMD until this TMD halts or demonstrates >>>>>>> non-halting behavior. >>>>>> >>>>>> But it must do this is [in] a finite number of steps, agreed? >>>>> >>>>> Yes. So it looks like we are getting somewhere. We are arriving >>>>> at mutual understanding. >>>> >>>> Yes! Whatever the decider does it much be able to make its >>>> determination in a finite number of steps. That's key and it's what >>>> >>>> H.q0 [M] W ⊢* H.qy when M halts on input W >>>> H.q0 [M] W ⊢* H.qn when M does not halt on input W >>> >>> Not quite. >>> H.qy if [M] W is a correct TMD that halts on its input >>> else >>> H.qn >> >> No, that's not the halting problem. That's the PO-halting problem and it > > It is the Halting Problem and you already agreed to this one. > >> may well have a decider (I'll let you know if tell me what a "correct" TDM >> is). If you simply mean the [M] must encode a TM, well that's right >> there in the notation. If that is not what you mean, the thread comes >> to a screeching halt. > > If the finite string is an English poem H.qn. > If the finite string is Pathological-self-reference(Olcott 2004) then H.qn > If the finite string is a correct TMD that does not halt then H.qn No, this is not the halting problem. I am very happy you have sorted out the PO-halting problem to your satisfaction, but you are not saying anything interesting about /the/ halting problem. It's defined in every single textbook on the subject. If I have agrees to this being the halting problem than I was simply wrong. I won't ask you to say where I agreed to it since you rarely address direct questions, but if I did, I was wrong. The halting problem is the problem of deciding what strings represent encoded TMs and inputs where the encoded TM would halt when run with the encoded input. All other strings (those that don't encode TM/input pairs included) must be rejected. The middle category -- properly encoded computations that you don't like the look of -- must be decided according the halting of the computation, not any other criteria. (It's logically possible that all those middle category strings represent halting computations in which case you are talking about the same problem, but that seems unlikely form the word syou use. Why not just call them halting computations?) > This is the hardest part that everyone in the world failed to notice > since 1937, so it is okay if it takes you a while to understand this. Not at all. Ever single year I taught this material someone came up with this idea. It is, after all, a seemingly obvious way round what looks like a "trick" in the proof -- spot the tricksy cases and either reject them or put them into some third category (you have proposed both in the past). Maybe you were the student who came up with it when you were taught this at university, but there is always someone who does. > It even fooled me for 3000 hours over a dozen years. Until 2016 or 2017 > I always thought that the Pathological Self-reference(Olcott 2004) came > from the infinite loop appended to the (qy) state. > >> >> (There is a decider for strings of the form [M] for some TM M so it >> makes no difference what version of the HP you consider. If you insist >> on the "full" version you have to drop the rather convenient [M] >> notation and say >> >> H.q0 V W ⊢* H.qy iff V encodes a machine M that halts on input W >> H.q0 V W ⊢* H.qn otherwise) >> > > That way of saying it has a semantic gap that ignores the PSR error. Or that you are addressing a different problem. That's fine. If you want to treat some reject a set of strings because of some other criterion (PSR as you call it), that makes it a different problem. I see know that the "semantic gap" is simply that the halting problem is not the problem you are talking about. > The Truth is that every correct halt decider must abort the halt > evaluation sequence specified by H [Ĥx] [Ĥx] before any halting decision > is made because the halt evaluation sequence specifies infinite > recursion. That may well be what you want for the PO-halting problem. I'm not interesting in it. >>>> means. >>>> >>>> H^ (built from H' built from some H meeting this specification) just >>>> copies it's input and then (from the state you helpful renamed H^.qx) >>>> behaves like H'. H' behaves like H right up until the last extra states >>>> that were added to H. >>>> >>>> So now I can no longer see what part of the proof is bothering you. We >>>> have >>> >>> You have to actually pay very close attention to what I am actually saying >>> and not leap ahead to what you think that I am saying. >>> >>> H' is dead off topic done. >>> H^ is dead off topic done. >> >> No, they are how the proof works. You can't tell me what part of the >> proof is still giving you trouble if you think two key constructs are >> off topic. They are the very core of the proof you claim to reject. > > I am and only will talk about H [Ĥx] [Ĥx]. OK. It has nothing to do with the proof of the halting theorem. <snip> >>> H^x is H with only the H^ states H^ prepended to H and none of the H' >>> states appended. >>> I have said this at least 20 times so it is really not that hard to >>> get this point. >> >> H^x does not appear in the proof. I asked what part of the proof is >> still bothering you. I wrote out the last steps since you have finally >> accepted the step that seemed to be holding you up. > > I simplified the proof to get rid of a possible source of endless > digression. I saw no proof of the halting theorem. And it seems you are not even talking about the same theorem. The PO-halting problem will have a PO-halting theorem of some sort but I don't know what it is and I don't care. I doubt any one else does either. > The same problem exists in the original proof, yet with the extraneous > complexity** of the infinite loop appended to otherwise final state (qy). > > ** 1999 Turing Award winner Fred Brooks inessential complexity. > The only way that I can solve these enormously difficult problems > is to boil them down to their (Fred Brooks) essence. > >> >>>> H^.q0 W |-* H^.qx W W |-* H^.qy oo if W encodes a TM that halts on W >>>> H^.q0 W |-* H^.qx W W |-* H^.qn otherwise >>>> >>>> Set W=[H^] in these lines to get this: >>>> >>>> H^.q0 [H^] |-* H^.qx [H^] [H^] |-* H^.qy oo >>>> >>>> if [H^] encodes a TM that halts on [H^] and >>>> >>>> H^.q0 [H^] |-* H^.qx [H^] [H^] |-* H^.qn >>>> >>>> otherwise. From this it's clear that H^ [H^] is a computation that does >>>> not halt if [H^] encodes a machine that halts on input [H^], or it is a >>>> computation that does halt if [H^] doesn't encode a machine that halts >>>> on input [H^]. No? >> >> No doubt you read these words very carefully (as you expect me to do >> with yours) so I wonder why you were not able to point out the flaw in >> the logic. We have what could be called "trace equations" that I don't >> think you dispute and they show the behaviour of H^ [H^] (were it to >> exist) leads to a contradiction. I really can't see why you still >> reject this clear and simple argument, and you are not helping by >> refusing to say which step in the chain you dispute. > > H [Ĥx] [Ĥx2] becomes > [Ĥx] [Ĥx2] [Ĥx3] becomes > [Ĥx2] [Ĥx3] [Ĥx4] becomes > [Ĥx3] [Ĥx4] [Ĥx5] becomes on and on > because every halt decider can only base its halting decision on its input > pair and each TMD in the infinite sequence requires its own input pair None of that has any relevance to the proof you claimed to reject. (It happens to be wrong, but since it's irrelevant, I won't waste more time trying to explain to you why it's wrong). > (As I said March 11, 2017 @ 3:13 PM in comp.theory). > >> >> <snip> >>>> For many posts you adamantly refused to accept that H^ always got to >>>> state qy or state qn, yet you kept saying that it did using this >>>> notation. What possible interpretation can there be other than you did >>>> not know what you were writing? >>> >>> Now that I have fully elaborated all of the nuances it turns out >>> that I was right all along. When H performs a debug trace on Ĥx >>> it aborts this trace before Ĥx ever gets to Ĥx.qy or Ĥx.qn. >> >> The proof makes no reference H^x. You need to say which step of the >> proof is still bothering you. H^ /does/ always get to either qy or qn. >> What some other machine might do is irrelevant. > > Bottom of page 319 verbatim > q0 Wm ⊢* Ĥ q0 Wm Wm ⊢* Ĥ ∞ > q0 Wm ⊢* Ĥ q0 Wm Wm ⊢* Ĥ y1 qn y2 > > Corrected, simplified, and clarified > Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qy ∞ > Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qn No, you broke the proof by inventing a new construction. You now even have a way out -- you can accept the proof because it shows there is not halt decider. You have been talking about a PO-halt decider, and they may well exist. > (1) I corrected his specified erroneous second start state > (2) I got rid of the tape specification at qn > (3) I made each state labeled with its machine name using dot notation > > When I refer to Ĥ.qx this is specified in Linz as a second start > state. Yes, that typo (or error or whatever) in the book was fixed long ago. The problem is you have stopped talking about the proof now that this point has been cleared up. >>> Ĥx [Ĥx] [Ĥx] specifies the pathological self-reference(Olcott 2004) >>> and the halt evaluation is aborted with a transition to H.qn. H^x transitions to qy for that input. You should know -- you inverted this construction. Obviously this mistake is not important because nothing about H^x says anything about the proof of the halting theorem. >> Whatever H^x does has no bearing on the key question. Which part of the >> proof that you have so very nearly understood do you reject as invalid? > > I can't even specify the debug trace of Ĥ [Ĥ] [Ĥ] because Linz has > incorrectly specified two start states. Yes, we know about that. You have been correctly specifying H' and H^ for some time now, so there is no need to get stuck on this typo. After all, you claim to know about all proofs of this theorem. If this typo is you only objection, I am content -- it means you accept my corrected version. >> H^x may be how you go on to resolve what you see as a problem, but if >> you want to claim that the proof is incorrect you must point out >> which step you think does not follow form the previous ones. > > It is specified right here in the Linz notation: > q0 Wm ⊢* Ĥ q0 Wm Wm, the execution trace of Wm Wm by Ĥ specifies > an infinitely recursive evaluation sequence: > Ĥ Wm Wm2 > Wm Wm2 Wm3 > Wm2 Wm3 Wm4 > Wm3 Wm4 Wm5... Yes, we all know about that. I wrote out the corrected proof for you. If your only objection is the typo in Linz, you have nothing. Is that all you have been complaining about? If so, why have you not accepted my corrected version? After all, it's a theorem about a problem you appear not to be interested in anymore. Accepting the corrected proof says nothing about the PO-halting problem. >>>> However, it does not define a Turning machine and you need specify in >>>> what cases each line applies. >>>> >>>> The rest of the post seems odd to me now that you agree that, to be a >>>> halt decider, as assumed by the proof, H must make its determination in >>>> a finite number of steps. The most helpful reply would be for you to >>>> say what part of the proof now bothers you. Maybe you could just mark >>>> the part above where you come unstuck? >>> >>> None of it bothers me, I simply found out where it went wrong, how and why >>> it is incorrect. >> >> Of course something about it bothers you -- you don't accept it. You >> can just reject it by simply saying you'll simply never believe it, but >> no one will take that seriously. You need to point out which step is >> the one you don't accept. > > I am not bothered by the question: "What time is it (yes or no)?" > I simply reject it as incorrect. That's not an answer. If you can't say what step you reject in the reasoning of the proof I wrote out, you have nothing. >>> I posted the answer way back in March 11, 2017 @ 3:13 PM in comp.theory. >>> All of the HP proofs inherently specify an infinitely recursive >>> evaluation sequence because each TM\D must have its own TMD / input >>> pair. >> >> That is not a step in the proof. You can't refute a sound proof with >> waffle. One of the steps must be wrong. If this notion of "infinitely >> recursive evaluation" makes some step of the proof wrong, that's what >> you need to point out. Otherwise, whatever it means, it has no bearing >> on the argument. > > It is only the conclusion of the proof that is wrong. So there is no step you can point to which does not follow logically from the previous ones. That means you have nothing. > H [Ĥx] [Ĥx] correctly decides that this is erroneous. H must accept that input. It is supposed to be a halting decider, and H^x halts on all inputs. Of course a PO-halt decider can do what it likes with the instance, but a decider for the halting problem must accept it. And, finally, H^x does not exist because it is derived form a class of machine that is empty. >>>> <snip> >>>>> I am very pleased with the progress that we have made. I think that we >>>>> are finally coming to a very significant mutual understanding. >>>> >>>> Maybe. I am, however, now not sure what part of the proof is bothering >>>> you. The most progress would my made were you to simply point out the >>>> step in the reasoning you think is wrong. >>> >>> I have already done that many times in may ways. That is OK that >>> you don't get it yet it took me decades and thousands of hours. >> >> Ah, the old, I did it already ploy. So you won't say which step you >> think is wrong by simply writing "THIS!!!" under the line you don't >> accept? I wrote out the rest of the proof so you could do just that. >> >>>> Take the argument and just >>>> put a **THIS!** at the bit you don't accept. I fear that instead of >>>> doing that you will write lots of words. >>> >>> THIS: That all HP proof inherently specify an infinitely recursive >>> set of TMD / input pairs because every TMD in this sequence requires >>> its own TMD / Input pair. >> >> That's not a step in the proof. I wrote it out for you so you could >> very simply say which step you reject. > > Bottom of page 319 verbatim > q0 Wm ⊢* Ĥ q0 Wm Wm > q0 Wm ⊢* Ĥ q0 Wm Wm > > The execution trace of Ĥ Wm Wm at this point in is specification. Yes, we all know about that. I wrote out the corrected proof for you. If your only complaint is the typo in the book, you have nothing. >>> I will write it up more formally and publish it to www.researchgate.net. >>> The one key piece that is missing is a really good abstract. <snip> >>>>> If I am >>>>> eventually proved correct I will cite you as my most valuable reviewer >>>>> of all Halting Problem related discussions. >>>> >>>> If you publish anything, I would very much appreciate it if you did not >>>> use my name in any way. This includes blog posts and so on. I know I >>>> can not stop you, but I hope you will honour this request. >>> >>> So if I am correct and have correctly refuted the Halting Problem proofs >>> you want to remain anonymous? >>> Its a little too late for that because of USENET. >> >> I did not say that. I do not want or need to be anonymous here because >> here I can defend myself. If you publish a paper I have no right of >> reply. You could publish any old rubbish and my name would then be >> associated with it. Will you accept my request? >> >> If you answer no other question in the reply, please explicitly answer >> this one. > > When I say publish I mean like in the Journal of the ACM. You referred to a self-publishing site. Obviously I have no worries about the JACM -- they don't publish junk, but researchgate.net may well do. > If I am validated and published and asked who helped review > my work I will say it was reviewed on USENET by various reviewers. Good enough, I suppose. -- Ben.
Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Necessary sequence of halt decider's inference chain George Greene <greeneg@email.unc.edu> - 2018-02-09 11:34 -0800
Re: Necessary sequence of halt decider's inference chain peteolcott <peterolcott2@gmail.com> - 2018-02-09 13:15 -0800
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-09 21:40 +0000
Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-09 23:48 -0600
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:57 +0000
Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:52 -0600
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 17:06 +0000
Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-11 00:36 -0600
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-11 16:13 +0000
Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-12 20:34 -0600
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 04:18 +0000
Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-13 10:03 -0600
Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 17:13 +0000
Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-13 16:59 -0800
Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-12 21:36 -0800
csiph-web