Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Simulation vs. Execution in the Halting Problem Date: Sun, 8 Jun 2025 08:57:05 -0400 Organization: A noiseless patient Spider Lines: 151 Message-ID: <10241b0$3rjen$1@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> <10237v8$3m1uq$1@dont-email.me> <10238o7$3m1s3$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 08 Jun 2025 14:57:04 +0200 (CEST) Injection-Info: dont-email.me; posting-host="1f869fb7b9bf7e087039c46933856a8a"; logging-data="4050391"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19J+sH1ZQIfskxT1sPIHMUE" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:YIbGFuGw5v5ho2pdLih9utQCwZs= In-Reply-To: <10238o7$3m1s3$1@dont-email.me> Content-Language: en-US On 6/8/2025 1:57 AM, olcott wrote: > On 6/8/2025 12:44 AM, Mikko wrote: >> On 2025-06-04 16:03:24 +0000, olcott said: >> >>> 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() > > dbush insists that it is required. > > then that entails > that HHH must report on the behavior of its caller.>> This is not > allowed even if it was possible. It is both allowed and possible: int H1(void *p) { return 1; } void D1() { H1(D1); } int main() { H1(D1); } H1(D1) correctly reports that the directly executed D1 halts. >> >> That prohibition is not in any relevant specification. The correctness >> criterion is a comparison of the answer given by the decider cnadidate >> to a complete execution of the computation. >> > >