Path: ...!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: Sat, 8 Jun 2024 08:43:17 -0500
Organization: A noiseless patient Spider
Lines: 172
Message-ID: <v41n5l$2kanc$7@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>
 <v40hlv$3bc44$2@i2pn2.org> <v40jkr$2elkd$5@dont-email.me>
 <v41kr9$3cg3t$10@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 08 Jun 2024 15:43:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="99ea1b6838dd1404bad406fc122dbf0f";
	logging-data="2763500"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18QqLQM2WG6Ygu7uGPjn4nc"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:n9jKMK0Bl3oazxirbPWjh2+2Yig=
Content-Language: en-US
In-Reply-To: <v41kr9$3cg3t$10@i2pn2.org>
Bytes: 10970

On 6/8/2024 8:03 AM, Richard Damon wrote:
> On 6/7/24 11:36 PM, olcott wrote:
>> On 6/7/2024 10:03 PM, Richard Damon wrote:
>>> On 6/7/24 10: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. 
>>>> 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.
>>>>
>>>> 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.  That forces him to claim there 
>>>> are two different behaviours [/beyond/ the simple truncation of the 
>>>> aborted trace] for the one computation, and to come up with some 
>>>> Words to justify that position (like "pathological self reference", 
>>>> subjective questions) and then More Words to say that his other 
>>>> Words are "the true meaning of halting" etc. etc.  All nonsense 
>>>> flowing from not being able to accept his rule is just wrong.
>>>>
>>>>
>>>> Mike.
>>>>
>>>
>>> The last time I remember him actually trying to answer, the 
>>> difference was that the order of who started mattered, because D(D) 
>>> calling H(D,D) meant that the H(D,D) that was called doesn't get 
>>> stuck in the loop, but recognizes the loop and gets out, while when 
>>> H(D,D) simulated D(D) and that first H(D,D) sees that the simulated 
>>> H(D,D) would just get into a loop, that incorrect decision becomes 
>>> the actual behavior of that simulated H(D,D).
>>>
>>> So it is always the first H(D,D) that returns, and the second one 
>>> doesn't, which just proes that is can't be a pure function, or that 
>>> rule doesn't apply to functions whose simulation has been aborted.
>>>
>>> Of course he also think that aborting th simulation mean that hte 
>>> machine being simulate had its plug pulled at that point, so it isn't 
>>> proper to look at the direct execution after that,
>>>
>>> He clearly doesn't seem to understand how these sorts of machines work.
>>
>> DD(DD) is just like infinite recursion that gets terminated at
>> its second recursive call. DD(DD) halts only because HH(DD,DD)
>> correctly determines that its input DOES NOT HALT.
> 
> Except a potentially infinite loop that has code that breaks out of that 
> loop will halt.
> 

<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

========== REMAINDER OF ARTICLE TRUNCATED ==========