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-11 16:13 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <874lmnjyhc.fsf@bsb.me.uk> (permalink) |
| References | (4 earlier) <2vWdnW0EN54oGuPHnZ2dnUU7-RPNnZ2d@giganews.com> <87sha9ngsu.fsf@bsb.me.uk> <htGdnTKFV8y4iOLHnZ2dnUU7-bHNnZ2d@giganews.com> <87mv0gn593.fsf@bsb.me.uk> <JdCdna8MAbPHeeLHnZ2dnUU7-aXNnZ2d@giganews.com> |
Cross-posted to 2 groups.
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 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 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? <snip> >>> Definition of Turing Machine H (state transition sequence) >>> H.q0 Wm W ⊢* H.qy >>> H.q0 Wm W ⊢* H.qn >> >> No. Stop using this notation until you have learned it. > > I know exactly what this notation means and it really seems dishonest > of you to say otherwise. It does /not/ define a Turning machine. And without extra annotations it does not even say what sort of machine H is. When you put those annotation back it describes behaviour -- it does define a machine. >>> Definition of Turing Machine Ĥx (state transition sequence) >>> Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qy // NO LOOP >>> Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qn // NO LOOP HERE EITHER >> >> No. Stop using this notation until you have learned it. > > You know that I must know what this triviality means > Quit being so damned disrespectful! 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? 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? <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. 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. > 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. -- 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