Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Simulation vs. Execution in the Halting Problem --- Linz Date: Sat, 31 May 2025 12:20:40 -0500 Organization: A noiseless patient Spider Lines: 166 Message-ID: <101fdp8$19tqq$1@dont-email.me> References: <101a7uv$3vfam$5@dont-email.me> <101br7m$db03$1@dont-email.me> <101cjk7$hfof$7@dont-email.me> <101e8ak$vhu7$1@dont-email.me> <75ebd63c01b3f351101ade56b5033804913220fa@i2pn2.org> <101fbn1$173bb$12@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 31 May 2025 19:20:40 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c9a131a468f55446a50ed4b18f7c4193"; logging-data="1374042"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ep/aBoUV7+ZAi1JzzUAmE" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:2xCNbgyBOp5UrkTN3p5l9abvqTA= In-Reply-To: X-Antivirus: Norton (VPS 250531-2, 5/31/2025), Outbound message X-Antivirus-Status: Clean Content-Language: en-US On 5/31/2025 12:05 PM, Mr Flibble wrote: > On Sat, 31 May 2025 11:45:21 -0500, olcott wrote: > >> On 5/31/2025 7:35 AM, Richard Damon wrote: >>> On 5/31/25 2:41 AM, olcott wrote: >>>> On 5/30/2025 8:16 PM, Richard Damon wrote: >>>>> On 5/30/25 11:41 AM, olcott wrote: >>>>>> 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. >>>>> >>>>> Nope. Where does it say that? >>>>> >>>>> >>>> _DDD() >>>> [00002192] 55             push ebp [00002193] 8bec           mov >>>> ebp,esp [00002195] 6892210000     push 00002192 [0000219a] >>>> e833f4ffff     call 000015d2  // call HHH [0000219f] 83c404 >>>> add esp,+04 [000021a2] 5d             pop ebp [000021a3] >>>> c3             ret Size in bytes:(0018) [000021a3] >>>> >>>> DDD emulated by HHH must be aborted.   // otherwise infinite recursion >>>> DDD emulated by HHH1 need not be aborted. >>>> >>>> >>> No, nether HHH or HHH1 can correctly emulate this input, as it is >>> incomplete, andt eh call HHH is IMPOSSIBLE to emulate in this input, as >>> its target is not in the input, so any action that looks elsewhere for >>> it is just not emulating THIS INPUT. >>> >>> Sorry, your acknoldegement that you DDD just isn't a program means that >>> its representation is NOT correctly emulatable. >>> >>> Fix that issue by including in the input the code of the HHH that >>> calling it, and we find that HHH just doesn't correctly emulate it, as >>> it has been defined, in halt7.c, to chose to abort at a spot where the >>> program does not stop. >>> >>> Of course, in your mind HHH isn't a program either, as you refuse to >>> accept that it must be a single program. Note, an infinite set of >>> programs is not A program. >>> >>> >>> Thus, you have admitted that your whole system of logic is based on >>> using incorrect definitions and lies. >>> >>>>> Your problem is you don't understand that the only things you can >>>>> correctly simulate are PROGRAMS, which mean they include all of their >>>>> code, which is also expressed in the input given to the simulator. >>>>> >>>>> >>>>>>> Whether it actually is depends on the quality of the simulator. >>>>>>> There is no exception for the case when the simulator is called. If >>>>>>> the behaviour in the simulation is different from a real execution >>>>>>> then the simulation is wrong. >>>>>>> >>>>>>> >>>>>> A function that calls its own simulator specifies different behavior >>>>>> than a function that does not call its own simulator. >>>>> >>>>> No it doesn't, as we can only be talking about programs, and programs >>>>> don't know who "their simulator" is, only what simulator they were >>>>> built to use. >>>>> >>>>> >>>>>>> One of the advantages of Turing machines is that there is no >>>>>>> possibility to call anything so the effect of calling the simulator >>>>>>> need not be considered. >>>>>>> >>>>>>> >>>>>> The same issue occurs in the Linz proof, it is merely more difficult >>>>>> to see. The correctly simulated ⟨Ĥ⟩ ⟨Ĥ⟩ cannot possibly reach > its >>>>>> own simulated final halt state ⟨Ĥ.qn⟩ >>>>> >>>>> What "Issue"? Your problme is you don't understand what you are >>>>> taling about. >>>>> >>>>> >>>>>> When Ĥ is applied to ⟨Ĥ⟩ >>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ Ĥ.q0 ⟨Ĥ⟩ ⊢* > embedded_H ⟨Ĥ⟩ >>>>>> ⟨Ĥ⟩ ⊢* Ĥ.qn >>>>> >>>>> Why did the copy of H change to being called "embedded_H"? >>>>> >>>>> >>>> I am using cleaner notational conventions. >>> >>> How is using two names for the same thing cleaner? >>> >>> >>>> >>>>>> (a) Ĥ copies its input ⟨Ĥ⟩ >>>>>> (b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ >>>>>> (c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ >>>>>> (d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ >>>>>> (e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ >>>>>> (f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ >>>>>> (g) goto (d) with one more level of simulation >>>>>> >>>>>> >>>>> Which then gets stop when the embedded_H invoked at the first >>>>> invocation of (b) doing step (c) decides to abort its emulation. >>>>> >>>>> >>>> I have it emulate one more level before stopping. >>>> It would stop at (e). >>> >>> Rigth, so you go (a) (b) (c) (e) (h) return to H^.qn (i) H^ Halts >>> >>> Thus showing the input is non-halting. >>> >>> >> *EVERYONE ALWAYS GETS THIS WRONG* >> >> int main() >> { >> DDD(); // The HHH that DDD calls is not supposed to >> } // report on the behavior of its caller, nitwit >> >> Likewise embedded_H is not supposed to report on the behavior of the >> computation that itself is embedded within. > > I think I see where you are going wrong: HHH has to call DDD in main(); > HHH has to be the outermost context for a halting result of NON-HALTING to > be valid. > > /Flibble > > /Flibble It is always correct for every HHH(DDD) to reject its input as specifying a non-halting sequence of configurations. The fact that the directly executed DDD() that calls HHH(DDD) does halt is none-of-the-business of HHH. HHH is only accountable for the behavior that its actual input actually specifies. *This seems to be brand new computer science* -- Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer