Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: "Fred. Zwarts" Newsgroups: comp.theory Subject: Re: Simulation vs. Execution in the Halting Problem Date: Fri, 6 Jun 2025 10:36:05 +0200 Organization: A noiseless patient Spider Lines: 139 Message-ID: <101u99l$251rf$4@dont-email.me> References: <101a7uv$3vfam$5@dont-email.me> <101br7m$db03$1@dont-email.me> <101cjk7$hfof$7@dont-email.me> <101hdjt$21ui2$1@dont-email.me> <101iheg$2h3fr$1@dont-email.me> <1e5e5837ae9e60daa16e5fef3693ff424c1049d2@i2pn2.org> <101j60c$2urhr$3@dont-email.me> <101jiah$33qt3$1@dont-email.me> <101khgk$3bfvj$7@dont-email.me> <101m9fs$3sq20$1@dont-email.me> <101nlof$7qau$9@dont-email.me> <101osfh$mj67$1@dont-email.me> <101pqoc$ta6v$6@dont-email.me> <101rgde$1d34j$3@dont-email.me> <101sehk$1kh2e$3@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 06 Jun 2025 10:36:06 +0200 (CEST) Injection-Info: dont-email.me; posting-host="e0264a7f49952eafc22259eeb7677921"; logging-data="2262895"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19hlImrpQbacpNnyAQHqf8x" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ZoQi5MWW/66QeRj64yZGdnlknKQ= In-Reply-To: <101sehk$1kh2e$3@dont-email.me> Content-Language: nl, en-GB Bytes: 7521 Op 05.jun.2025 om 17:53 schreef olcott: > On 6/5/2025 2:19 AM, Fred. Zwarts wrote: >> Op 04.jun.2025 om 18:03 schreef olcott: >>> On 6/4/2025 2:26 AM, Mikko wrote: >>>> On 2025-06-03 20:25:51 +0000, olcott said: >>>> >>>>> On 6/3/2025 2:50 AM, Mikko wrote: >>>>>> On 2025-06-02 15:55:00 +0000, olcott said: >>>>>> >>>>>>> On 6/2/2025 2:02 AM, Mikko wrote: >>>>>>>> On 2025-06-02 03:32:28 +0000, olcott said: >>>>>>>> >>>>>>>>> On 6/1/2025 8:19 PM, Richard Damon wrote: >>>>>>>>>> On 6/1/25 5:41 PM, olcott wrote: >>>>>>>>>>> On 6/1/2025 6:30 AM, Mikko wrote: >>>>>>>>>>>> On 2025-05-30 15:41:59 +0000, olcott said: >>>>>>>>>>>> >>>>>>>>>>>>> On 5/30/2025 3:45 AM, Mikko wrote: >>>>>>>>>>>>>> On 2025-05-29 18:10:39 +0000, olcott said: >>>>>>>>>>>>>> >>>>>>>>>>>>>>> On 5/29/2025 12:34 PM, Mr Flibble wrote: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> 🧠 Simulation vs. Execution in the Halting Problem >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> In the classical framework of computation theory (Turing >>>>>>>>>>>>>>>> machines), >>>>>>>>>>>>>>>> simulation is not equivalent to execution, though they >>>>>>>>>>>>>>>> can approximate one >>>>>>>>>>>>>>>> another. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> To the best of my knowledge a simulated input >>>>>>>>>>>>>>> always has the exact same behavior as the directly >>>>>>>>>>>>>>> executed input unless this simulated input calls >>>>>>>>>>>>>>> its own simulator. >>>>>>>>>>>>>> >>>>>>>>>>>>>> The simulation of the behaviour should be equivalent to >>>>>>>>>>>>>> the real >>>>>>>>>>>>>> behaviour. >>>>>>>>>>>>> >>>>>>>>>>>>> That is the same as saying a function with infinite >>>>>>>>>>>>> recursion must have the same behavior as a function >>>>>>>>>>>>> without infinite recursion. >>>>>>>>>>>> >>>>>>>>>>>> A function does not have a behaviour. A function has a value >>>>>>>>>>>> for >>>>>>>>>>>> every argument in its domain. >>>>>>>>>>>> >>>>>>>>>>>> A function is not recursive. A definition of a function can be >>>>>>>>>>>> recursive. There may be another way to define the same function >>>>>>>>>>>> without recursion. >>>>>>>>>>>> >>>>>>>>>>>> A definition of a function may use infinite recursion if it >>>>>>>>>>>> is also >>>>>>>>>>>> defined how that infinite recursion defines a value. >>>>>>>>>>>> >>>>>>>>>>>> Anyway, from the meaning of "simulation" follows that a >>>>>>>>>>>> simulation >>>>>>>>>>>> of a behaviour is (at least in some sense) similar to the real >>>>>>>>>>>> behaviour. Otherwise no simulation has happened. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> void DDD() >>>>>>>>>>> { >>>>>>>>>>>    HHH(DDD); >>>>>>>>>>>    return; >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> The *input* to simulating termination analyzer HHH(DDD) >>>>>>>>>>> specifies recursive simulation that can never reach its >>>>>>>>>>> *simulated "return" instruction final halt state* >>>>>>>>>>> >>>>>>>>>>> *Every rebuttal to this changes the words* >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> No it doesn't, as HHH is defined to abort and simulation after >>>>>>>>>> finite time, and thus only does finite simulation. >>>>>>>>>> >>>>>>>>> >>>>>>>>> See right there you changed the words. >>>>>>>>> I said nothing about finite or infinite simulation. >>>>>>>>> You said that I am wrong about something that I didn't even say. >>>>>>>> >>>>>>>> Again you are trying a sraw man deception. RIchard Damon did not >>>>>>>> change >>>>>>>> your words, he only wrote his own. He did not claim that you >>>>>>>> said anything >>>>>>>> about "finite" or "infinite" but that you should understand the >>>>>>>> difference. >>>>>>> >>>>>>> Unlike most people here I do understand that not >>>>>>> possibly reaching a final halt state *is* non-halting behavior. >>>>>> >>>>>> You don't understand it correctly. Whether a computation is >>>>>> halting is a >>>>>> feature of the computation, not a particular exectuion of that >>>>>> coputation. >>>>>> A halting computation is a halting computation even if its >>>>>> execution is >>>>>> discontinued before reaching the final halt state. >>>>> >>>>> int main() >>>>> { >>>>>    DDD(); // Do you understand that the HHH(DDD) that this DDD >>>>> }        // calls is only accountable for the behavior of its >>>>>           // input, and thus NOT accountable for the behavior >>>>>           // of its caller? >>>> >>>> I don't set any requirements on HHH. I just note that if HHH does not >>>> return a value that means "halts" it is not a halt decider and not >>>> even a partial halt decider, because the direct execution of DDD has >>>> been shown to halt. >>>> >>> >>> If HHH(DDD) is supposed to report on the behavior >>> of the direct execution of DDD() then that entails >>> that HHH must report on the behavior of its caller. >>> This is not allowed even if it was possible. >>> >> >> The definition of a correct report is to report about the input. Not >> about a hypothetical input. > > DDD simulated by HHH cannot possibly reach its "return" > instruction final halt state. DDD simulated by HHH derives > that actual behavior that the input to HHH(DDD) actually > specifies. > Counterfactual. The input specifies a DDD that calls a HHH that includes the code to abort and halt. That is the actual behaviour that is specified. But HHH does not see that, because its programmer is dreaming of a HHH that does not abort and uses that dream as a basis to abort the simulation before it can see the whole specification of the actual behaviour. It uses the behaviour of a dreamed (hypothetical) HHH, instead of the actual behaviour. That HHH fails to see the whole specification, does not change the fact that the input specifies an actual behaviour of a halting program. Sum(2,3) is supposed to compute the sum of 2 and 3. It is incorrect to process only the 2, only because due to a programming error it cannot reach the 3.