Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: DDD specifies recursive emulation to HHH and halting to HHH1 Date: Mon, 31 Mar 2025 11:47:01 +0300 Organization: - Lines: 69 Message-ID: References: <3ade9e84224ba9b99c7363e0e9b69181804b7daa@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 31 Mar 2025 10:47:01 +0200 (CEST) Injection-Info: dont-email.me; posting-host="9db5ebc22b0a66665dc12d47e37818b7"; logging-data="4044319"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18cvYM4hQ6FqawP9BwKtAwT" User-Agent: Unison/2.2 Cancel-Lock: sha1:pigQUOxflwOBCnbWwlbeFRE2/PM= Bytes: 4449 On 2025-03-30 20:32:07 +0000, olcott said: > On 3/30/2025 1:52 PM, Richard Damon wrote: >> On 3/30/25 2:27 PM, olcott wrote: >>> On 3/30/2025 3:12 AM, joes wrote: >>>> Am Sat, 29 Mar 2025 16:46:26 -0500 schrieb olcott: >>>>> On 3/29/2025 3:14 PM, dbush wrote: >>>>>> On 3/29/2025 4:01 PM, olcott wrote: >>>> >>>>>>> We can know that when this adapted UTM simulates a finite number of >>>>>>> steps of its input that this finite number of steps were simulated >>>>>>> correctly. >>>>>> And therefore does not do a correct UTM simulation that matches the >>>>>> behavior of the direct execution as it is incomplete. >>>>> It is dishonest to expect non-terminating inputs to complete. >>>> A complete simulation of a nonterminating input doesn't halt. >>>> >>>>>>>> 2) changing the input is not allowed >>>>>>> The input is unchanged. There never was any indication that the input >>>>>>> was in any way changed. >>>>>> False, if the starting function calls UTM and UTM changes, you're >>>>>> changing the input. >>>>> When UTM1 is a UTM that has been adapted to only simulate a finite >>>>> number of steps >>>> So not an UTM. >>>> >>>>> and input D calls UTM1 then the behavior of D simulated >>>>> by UTM1 never reaches its final halt state. >>>>> When D is simulated by ordinary UTM2 that D does not call Then D reaches >>>>> its final halt state. >>>> Doesn't matter if it calls it, but if the UTM halts. >>>> >>>>>> Changing the input is not allowed. >>>>> I never changed the input. D always calls UTM1. >>>>> thus is the same input to UTM1 as it is to UTM2. >>>> You changed UTM1, which is part of the input D. >>>> >>> >>> UTM1 simulates D that calls UTM1 >>> simulated D NEVER reaches final halt state >>> >>> UTM2 simulates D that calls UTM1 >>> simulated D ALWAYS reaches final halt state >>> >> >> Only because UTM1 isn't actually a UTM, but a LIE since it only does a >> partial simulation, not a complete as REQURIED by the definition of a >> UTM. >> > > _DDD() > [00002172] 55 push ebp ; housekeeping > [00002173] 8bec mov ebp,esp ; housekeeping > [00002175] 6872210000 push 00002172 ; push DDD > [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD) > [0000217f] 83c404 add esp,+04 > [00002182] 5d pop ebp > [00002183] c3 ret > Size in bytes:(0018) [00002183] > > DDD EMULATED BY HHH DOES SPECIFY THAT IT > CANNOT POSSIBLY REACH ITS OWN FINAL HALT STATE. No, it does not. HHH misintepretes, contrary to the semantics of x86, the specification to mean that. -- Mikko