Path: ...!feeds.phibee-telecom.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: How Partial Simulations correctly determine non-halting ---Ben's 10/2022 analysis Date: Sun, 9 Jun 2024 11:15:26 +0300 Organization: - Lines: 172 Message-ID: References: <87h6eamkgf.fsf@bsb.me.uk> <_gWdnbwuZPJP2sL7nZ2dnZfqn_GdnZ2d@brightview.co.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 09 Jun 2024 10:15:27 +0200 (CEST) Injection-Info: dont-email.me; posting-host="77c7217a9c7c64c7766c5a2e0efa49c1"; logging-data="3507287"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19IVd0BSdktlr1p+P+fWhXX" User-Agent: Unison/2.2 Cancel-Lock: sha1:GPjra1KVVyHk15tpXl+ipRuVV6U= Bytes: 11227 On 2024-06-08 13:43:17 +0000, olcott said: > 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. >> > > > 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. > > > No you are wrong. It does not make much sense to say "you are wrong" without saying about what and what is right instead. Besides, there should be either a comma after "No" or the word "not" after "are". We may guess from context which one you meant but a guess is only a guess. -- Mikko