Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: How Partial Simulations correctly determine non-halting ---Ben's
 10/2022 analysis
Date: Fri, 7 Jun 2024 22:16:54 -0500
Organization: A noiseless patient Spider
Lines: 188
Message-ID: <v40if6$2elkd$3@dont-email.me>
References: <v3j20v$3gm10$2@dont-email.me>
 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <87h6eamkgf.fsf@bsb.me.uk> <v3kcdj$3stk9$1@dont-email.me>
 <v3l7uo$13cp$8@dont-email.me> <v3lcat$228t$3@dont-email.me>
 <v3mq9j$chc3$1@dont-email.me> <v3mrli$chc4$1@dont-email.me>
 <_gWdnbwuZPJP2sL7nZ2dnZfqn_GdnZ2d@brightview.co.uk>
 <v3nkqr$h7f9$3@dont-email.me> <v3p4ka$sk6h$1@dont-email.me>
 <v3pp7p$v133$8@dont-email.me> <v3s27e$1f9kd$1@dont-email.me>
 <v3sf1n$1gra7$11@dont-email.me> <v3sjo9$1ialb$1@dont-email.me>
 <v3skoo$1iedv$1@dont-email.me> <v3u9ej$1v7rn$1@dont-email.me>
 <v3v6i7$23l33$1@dont-email.me> <v3v70o$21qlc$3@dont-email.me>
 <v3v7j8$242e9$2@dont-email.me> <v3v7qh$21qlc$4@dont-email.me>
 <v3v8f9$242e9$3@dont-email.me> <v3v96e$39q1p$4@i2pn2.org>
 <v3v9ll$242e9$7@dont-email.me> <v3vcqi$3a78f$1@i2pn2.org>
 <HhucnUC3H-bzWP77nZ2dnZfqn_qdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 08 Jun 2024 05:16:55 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="99ea1b6838dd1404bad406fc122dbf0f";
	logging-data="2578061"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+SEigOD2rQb+cqEstL9ATF"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:/xQCe4vTMoNDAPoFfWGOqJy/TbQ=
In-Reply-To: <HhucnUC3H-bzWP77nZ2dnZfqn_qdnZ2d@brightview.co.uk>
Content-Language: en-US
Bytes: 10809

On 6/7/2024 9:43 PM, Mike Terry wrote:
> On 07/06/2024 17:34, joes wrote:
>> Am Fri, 07 Jun 2024 10:40:37 -0500 schrieb olcott:
>>> On 6/7/2024 10:32 AM, joes wrote:
>>>> Am Fri, 07 Jun 2024 10:20:09 -0500 schrieb olcott:
>>>>> On 6/7/2024 10:09 AM, Python wrote:
>>>>>> Le 07/06/2024 à 17:05, olcott a écrit :
>>>>>>> On 6/7/2024 9:55 AM, Python wrote:
>>>>>>>> Le 07/06/2024 à 16:47, olcott a écrit :
>>
>>>>>>>>> The issue here is that I proved that DD correctly simulated by HH
>>>>>>>>> has different behavior than the directly executed DD(DD) and
>>>>>>>>> everyone's "rebuttal" to this proof is to simply ignore it.
>>>>>>> When you actually try to form a rebuttal of the above you will see
>>>>>>> that I am correct. So far everyone simply ignores the proof that I
>>>>>>> am correct as their only rebuttal.
>>>>> A {correct simulation} means that each instruction of the above x86
>>>>> machine language of DD is correctly simulated by HH and simulated in
>>>>> the correct order.
>>>> And to the end. Thus it can't behave differently than direct execution.
>>> You must not be very good at programming if you believe that
>>> Infinite_Recursion must be simulated "to the end"
>> As I said before, if there is no end the simulation can't end either.
> 
> PO chooses to leave his terminology ambiguous, so we have 1000 post 
> threads perpetuated by little more than verbal misunderstandings.
> 
> All PO's "simulating halt deciders" (SHD) are actually "partial 
> simulating partial halt deciders":
> They partially simulate their input computation, while monitoring the 
> simulation state for patterns which *PO* just believes (without proof) 
> indicate non-halting.  When such a pattern is detected, the SHD abandons 
> its simulating activity ["aborts" its simulation], and returns 
> nonhalting.  Also, PO does not claim that his SHDs decide all inputs 
> correctly - or even that they halt for all inputs (which a decider 
> must).  He is really just interested in the H(D,D) case.
> 
> PO has a couple of such rules/patterns, and at least one of them is 
> sound: the "tight loop" pattern.  If an input (P,I) contains a tight 
> loop (like "LOOP: goto LOOP"), and assuming PO has coded the rule 
> correctly, his H/HH will detect the tight loop while simulating the code 
> and correctly return non-halting.  In this scenario we have a 
> non-terminating computation, but PO's /partial/ simulation obviously 
> ends through aborting the target.  THERE'S NOTHING WRONG WITH THAT.  If 
> someone wants to claim "that's not valid simulation" then right or wrong 
> it's nothing more than a disagreement over use of terminology, and 
> nothing is achieved by that.
> 
> PO also has at least one /unsound/ rule: his "infinite recursive 
> simulation" rule.  That rule matches computations that in fact halt.  

The a sequence of configurations stops running because some
aspect of it has been abnormally terminated does not mean that
this sequence halts.

Discussing this aspect is ridiculously too complex until after
you first understand that DD is correctly simulated by HH.

We wasted three years on this because no one ever bothered
to see that I have conclusively proved that DD is correctly
simulated by HH at the x86 machine code level.

> Despite PO's colourful language like "...until H 'sees that the 
> simulation will never terminate unless blah blah'" and "...DD 'specifies 
> infinite recursion to HH'" and so on, the truth is simply that his H is 
> applying an unsound rule, which leads to it deciding incorrectly.)
> 
> And all the stuff about "correct simulations of DD by HH never reaching 
> line nn" might be correct if suitably interpreted (as /partial 
> simulations/ not reaching a simulated halt state, rather than the 
> /actual computation/ being examined), but its all logically irrelevent 
> having little to do with actual termination of a given computation.
> 
> What makes the SHD work or not work is the matching of rules (patterns 
> detected in the simulated computation states) that the SHD uses to 
> trigger an abort.  If a /sound/ rule matches, the SHD will decide 
> correctly. If an /unsound/ rule matches it may decide incorrectly (as 
> with PO's H(D,D)), or in other situations it might be correct "by fluke".
> 
> If PO's H used only sound rules, it would not decide input (D,D) 
> incorrectly - but unfortunately neither would it decide correctly - it 
> would never terminate /for that input/.  (I find that kind of neat...)
> 
>>
>>>>> Anyone claiming that HH should report on the behavior of the directly
>>>>> executed DD(DD) is requiring a violation of the above definition of
>>>>> correct simulation.
>>>> But those are the same. How does simulating something change it?
>>> It seems to boil down to you just don't know enough about programming
>>> otherwise it would occur to you that there cannot possibly exist any
>>> correct rebuttal to the following:
>> Answer the question. Why should the simulation differ from direct
>> execution?
> 
> [Let's assume code is properly restricted to exclude the complications 
> of "cheating" in PO's x86utm environment through use of mutable static 
> variables and the like.]
> 
> Obviously they wouldn't, except in so far as "partial simulation" 
> differs from "full simulation". I.e. all steps will match precisely, up 
> to the point where the partial simulation is abandoned.
> 
> And in PO's H(D,D) vs D(D) example that is exactly what the traces 
> show:  The simulated and direct traces match exactly, right up to the 
> point where H aborts the simulation.  (The full computation steps of 
> D(D) then proceeding further until D terminates a bit later.)
> 
> Even though I put the two traces side-by-side for PO, he still insists 
> the "behaviour is different".  Well, perhaps he just means that the H 
> simulation was abandonned whereas directly executed D(D) proceeded 
> further and eventually terminated?  If so, then /so what/?  I think his 
> problem here is nothing to do with /simulations/ not reaching whatever 
> line of code, but more the /reason/ that his H aborted - it matched his 
> (unsound) non-halting pattern, and he just really really really really 
> believes that pattern is sound.
> 

I have proven that DD correctly simulated by HH cannot possibly
stop unless aborted thus meeting this criteria:

Only these verbatim words were agreed to by MIT Professor Michael Sipser
<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

   H can abort its simulation of D and correctly report that D
   specifies a non-halting sequence of configurations.
</MIT Professor Sipser agreed to ONLY these verbatim words10/13/2022>

On 10/14/2022 7:44 PM, Ben Bacarisse wrote:
 > I don't think that is the shell game. PO really /has/ an H
 > (it's trivial to do for this one case) that correctly determines
 > that P(P) *would* never stop running *unless* aborted.

> So now he needs to account for two "verified facts":  1)  D(D) 
> computation never halts (/his unsound pattern matched!/)  2) D(D) 
> computation halts when run directly. 

DD correctly simulated by HH never halts.
Directly executed DD(DD) is not the behavior
of the input that HH held accountable for.

I incorporate by reference
(a) The x86 language
(b) The notion of an x86 emulator

(c) I provide this complete function

void DDD(int (*x)())
{
   HH(x, x);
}

_DDD()
[00001de2] 55         push ebp
[00001de3] 8bec       mov ebp,esp
[00001de5] 8b4508     mov eax,[ebp+08]
[00001de8] 50         push eax         ; push DD
[00001de9] 8b4d08     mov ecx,[ebp+08]
[00001dec] 51         push ecx         ; push DD
[00001ded] e890f5ffff call 00001382    ; call HH
[00001df2] 83c408     add esp,+08
[00001df5] 5d         pop ebp
========== REMAINDER OF ARTICLE TRUNCATED ==========