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 <mikko.levanto@iki.fi>
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: <v43oau$3b12n$1@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> <v41n5l$2kanc$7@dont-email.me>
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.
>> 
> 
> <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>
> 
> 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