Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups: comp.theory
Subject: Re: How the requirements that Professor Sipser agreed to are exactly
 met --- WDH
Date: Thu, 15 May 2025 01:36:21 +0100
Organization: A noiseless patient Spider
Lines: 135
Message-ID: <1003cu5$2p3g1$1@dont-email.me>
References: <vvte01$14pca$29@dont-email.me>
 <fceb852a146ff7238c5be7a0adf420474a8fb5df@i2pn2.org>
 <vvuc7a$1deu5$5@dont-email.me>
 <c5a47349d8625838f1ee2782c216e0ebf9223bc6@i2pn2.org>
 <vvuj6l$1j6s0$3@dont-email.me>
 <b78af2e0b52f178683b672b45ba1bc2012023aaf@i2pn2.org>
 <1000dlc$21dtc$5@dont-email.me> <1000qdb$24gr3$4@dont-email.me>
 <1000rir$24jh0$3@dont-email.me> <1000rqc$24gr3$7@dont-email.me>
 <1000son$24sr2$3@dont-email.me>
 <7947826fb84c9c8db49c392b305d395c3669907f@i2pn2.org>
 <1002dre$2i4bk$14@dont-email.me> <1002vp2$2mbr6$3@dont-email.me>
 <10030c3$2mivc$3@dont-email.me> <87h61mang3.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 15 May 2025 02:36:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="888b160797d405e6e8aa18420e8a2d49";
	logging-data="2919937"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+hRMVVzXWvD/SBfV4g0dyGlVoaLaNusM8="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:PyzTK2FDvIPpFHL+NoxibRpAXSw=
In-Reply-To: <87h61mang3.fsf@nosuchdomain.example.com>
Bytes: 7780

On 14/05/2025 22:31, Keith Thompson wrote:
> olcott <polcott333@gmail.com> writes:
>> On 5/14/2025 3:51 PM, dbush wrote:
>>> On 5/14/2025 11:45 AM, olcott wrote:
>>>> On 5/14/2025 6:20 AM, Richard Damon wrote:
>>>>>
>>>>> And since the DD that HHH is simulating WILL HALT when fully
>>>>> simulated (an action that HHH doesn't do)
>>>>
>>>> *NOT IN THE ACTUAL SPEC*
>>>> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>>       If simulating halt decider H correctly simulates its
>>>>       input D until H correctly determines that its simulated D
>>>>       would never stop running unless aborted then
>>>>
>>> That Sipser didn't agree what you think the above means:
>>>
>>
>> If that was actually true then you could provide an
>> alternative meaning for the exact words stated above.
>>
>> I keep challenging you to provide this alternative
>> meaning and you dodge because you know that you are
>> lying about there being any alternative meaning
>> FOR THE EXACT WORDS LISTED ABOVE.
> 
> No alternative meaning is needed, just a correct interpretation of the
> words (which appear to be incomplete).
> 
> The quoted sentence is cut off, something that I suspect you didn't
> notice.  Here's the full quotation from a previous article:
> 
>>> <Sipser approved abstract>
>>> MIT Professor Michael Sipser has agreed that the following verbatim
>>> paragraph is correct (he has not agreed to anything else in this
>>> paper):
>>>
>>> If simulating halt decider H correctly simulates its input D until H
>>> correctly determines that its simulated D would never stop running
>>> unless aborted then H can abort its simulation of D and correctly
>>> report that D specifies a non-halting sequence of configurations.
>>> </Sipser approved abstract>
> 
> **If** H correctly simulates its input in the manner you claim,
> **then** H can correctly report the halting status of D.  (That's a
> paraphrase that probably doesn't capture the full meaning; the full
> **quotation is above.)
> 
> To put it another way, If H correctly simulated its input in
> the manner you claim, then H could correctly report the halting
> status of D.
> 
> I'm not surprised that Sipser would agree to that.  The problem is
> that it's a conditional statement whose premise is impossible.
> 
> If an equilateral triangle had four sides, then each of its four
> vertices would be 90 degrees.  That doesn't actually mean that
> there exists an equilateral triangle with four 90-degree vertices,
> and in fact no such triangle exists.  Similarly, *if* a general
> halt decider existed, then there are a lot of things we could say
> about it -- but no general halt decider can exist.
> 
> I'm not quite 100% confident in my reasoning here.  I invite any
> actual experts in computational theory (not you, PO) to criticize
> what I've written.

I doubt that Sipser would be using your interpretation, relying on a false premise as a clever kind 
of logical loop-hole to basically fob someone off.

There is a natural (and correct) statement that Sipser is far more likely (I'd say) to have agreed to.

First you should understand the basic idea behind a "Simulating Halt Decider" (*SHD*) that 
/partially/ simulates its input, while observing each simulation step looking for certain 
halting/non-halting patterns in the simulation.  A simple (working) example here is an input which 
goes into a tight loop.  Going back to x86 world for this example, say the input (program to be 
decided) contains

   Input Code
   Address     Instruction
   ...
   00400000    push ebp
   00400001    mov ebp,esp
   00400003    sub esp,+24
   00400006    jmp 00400006    ; <===   jump to this instruction
   00400008    mov eax,[ebp+20]
   0040000b    mov ecx,[eax]
   ...

and during simulation, the SHD traces the computation steps, which reach the jmp instruction.  The 
observed simulated instruction trace might be something like:

   Inst.Ptr    Instruction
   00400000    push ebp
   00400001    mov ebp,esp
   00400003    sub esp,+24
   00400006    jmp 00400006       [A]
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   00400006    jmp 00400006
   ...

Clearly the SHD, observing the above, already has enough information after seeing step [A] to 
conclude that its target is going into a tight loop, and is never going to halt.  It can stop 
simulating and correctly decide "non-halting".

That is a valid design for a (partial) halt decider, and it is how an SHD works.  Sipser would be 
aware of this sort of approach, though likely under some name other than "SHD".

Now when we look at PO's Sipser quote:

--------- Sipser quote -----
   If simulating halt decider H correctly simulates its input D until H
   correctly determines that its simulated D would never stop running
   unless aborted then H can abort its simulation of D and correctly
   report that D specifies a non-halting sequence of configurations.
----------------------------

we can easily interpret that as saying exactly what I said a SHD does above.  It tells PO that in 
the tight loop example, H correctly simulates as far as [A], at which point it correctly determines 
that "its simulated input would never stop running unless aborted", so it can decide "non-halting".

All correct and natural, and no deliberately false premises to mislead PO.

PO's problem is his misinterpretation of "its simulated input would never stop running unless 
aborted".  In the case of his HHH/DD, the simulated input (DD) /does/ stop running if simulated far 
enough, but HHH simply /doesn't/ go far enough because PO has mistakenly decided he's seen some 
pattern that implies non-halting in the trace.  [A pattern akin to the "tight loop" pattern, except 
that the tight loop pattern is sound, while his pattern is unsound, matching on a halting input. 
Simples!]


Mike.