Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > sci.logic > #172431

Re: Necessary sequence of halt decider's inference chain

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.

Show all headers | View raw


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


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