Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Try and prove that DDD correctly emulated by HHH reaches its final halt state Date: Mon, 12 May 2025 09:36:01 -0500 Organization: A noiseless patient Spider Lines: 135 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 12 May 2025 16:36:02 +0200 (CEST) Injection-Info: dont-email.me; posting-host="15cac720ddbb61c7f6586fe023932af8"; logging-data="1205642"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+THKSQ0xI6ptpSNZJS4oUP" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:zwr06TVKPz9Nix+EFSTReD+4rtE= X-Antivirus-Status: Clean Content-Language: en-US In-Reply-To: X-Antivirus: Norton (VPS 250512-2, 5/12/2025), Outbound message Bytes: 7232 On 5/12/2025 2:39 AM, Mikko wrote: > On 2025-05-11 16:23:29 +0000, olcott said: > >> On 5/11/2025 4:20 AM, Mikko wrote: >>> On 2025-05-10 15:33:50 +0000, olcott said: >>> >>>> On 5/10/2025 2:40 AM, Mikko wrote: >>>>> On 2025-05-10 01:26:54 +0000, olcott said: >>>>> >>>>>> void DDD() >>>>>> { >>>>>>    HHH(DDD); >>>>>>    return; >>>>>> } >>>>>> >>>>>> _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] >>>>>> >>>>>> Try to show how DDD emulated by HHH according to the >>>>>> rules of the x86 language reaches its own "ret" >>>>>> instruction final halt state. >>>>> >>>>> If you do the impossible then everything happens, including >>>>> the reaching of the final "ret" instruction. In this case >>>>> the impossible is a correct emulation of DDD by HHH according >>>>> to the rules of the x86 language. >>>>> >>>> >>>> It is not impossible for DDD to be emulated >>>> by HHH according to the rules of the x86 language. >>> >>> You may call it possible or impossible but either way, HHH does >>> not emulate the final "ret" isntruction. >>> >>>> Here it is actually doing this. >>>> >>>> _DDD() >>>> [0000219e] 55             push ebp >>>> [0000219f] 8bec           mov ebp,esp >>>> [000021a1] 689e210000     push 0000219e >>>> [000021a6] e843f4ffff     call 000015ee >>>> [000021ab] 83c404         add esp,+04 >>>> [000021ae] 5d             pop ebp >>>> [000021af] c3             ret >>>> Size in bytes:(0018) [000021af] >>>> >>>> _main() >>>> [000021be] 55             push ebp >>>> [000021bf] 8bec           mov ebp,esp >>>> [000021c1] 689e210000     push 0000219e >>>> [000021c6] e823f4ffff     call 000015ee >>>> [000021cb] 83c404         add esp,+04 >>>> [000021ce] 50             push eax >>>> [000021cf] 685f070000     push 0000075f >>>> [000021d4] e8a5e5ffff     call 0000077e >>>> [000021d9] 83c408         add esp,+08 >>>> [000021dc] 33c0           xor eax,eax >>>> [000021de] 5d             pop ebp >>>> [000021df] c3             ret >>>> Size in bytes:(0034) [000021df] >>>> >>>>   machine   stack     stack     machine        assembly >>>>   address   address   data      code           language >>>>   ========  ========  ========  ============== ============= >>>> [000021be][00103872][00000000] 55             push ebp >>>> [000021bf][00103872][00000000] 8bec           mov ebp,esp >>>> [000021c1][0010386e][0000219e] 689e210000     push 0000219e // push DDD >>>> [000021c6][0010386a][000021cb] e823f4ffff     call 000015ee // call HHH >>>> New slave_stack at:103916 >>>> >>>> Begin Local Halt Decider Simulation   Execution Trace Stored at:11391e >>>> [0000219e][0011390e][00113912] 55             push ebp >>>> [0000219f][0011390e][00113912] 8bec           mov ebp,esp >>>> [000021a1][0011390a][0000219e] 689e210000     push 0000219e // push DDD >>>> [000021a6][00113906][000021ab] e843f4ffff     call 000015ee // call HHH >>>> >>>> The following shows the result of HHH emulating >>>> itself emulating DDD. x86utm is a cooperative >>>> multi-tasking operating system. >>>> >>>> New slave_stack at:14e33e >>>> [0000219e][0015e336][0015e33a] 55             push ebp >>>> [0000219f][0015e336][0015e33a] 8bec           mov ebp,esp >>>> [000021a1][0015e332][0000219e] 689e210000     push 0000219e // push DDD >>>> [000021a6][0015e32e][000021ab] e843f4ffff     call 000015ee // call HHH >>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped >>>> >>>> [000021cb][00103872][00000000] 83c404         add esp,+04 >>>> [000021ce][0010386e][00000000] 50             push eax >>>> [000021cf][0010386a][0000075f] 685f070000     push 0000075f >>>> [000021d4][0010386a][0000075f] e8a5e5ffff     call 0000077e >>>> Input_Halts = 0 >>>> [000021d9][00103872][00000000] 83c408         add esp,+08 >>>> [000021dc][00103872][00000000] 33c0           xor eax,eax >>>> [000021de][00103876][00000018] 5d             pop ebp >>>> [000021df][0010387a][00000000] c3             ret >>>> Number of Instructions Executed(10069) == 150 Pages >>> >>> Apparently you said that the last "ret" is not acutally emulated but >>> only its emulation is emulated. >>> >>> Your trace lacks the indication of which lines are actually trace lines >>> and which are output lines from the emulated program that only look like >>> trace lines. >> >> You must use the machine addresses to see what code >> is being emulated. New slave_stack indicate that >> a new process context has been created. Code following >> that is being emulated. > > Nowhere is said that a slave stack is disposed. Apparently no emulation > is ever completed. But your output is too defective to be sure. > >> New slave_stack at:14e33e indicates that HHH is >> about to emulate itself emulating DDD. > > But not to the completion of the emulated emulation. > When what is essentially infinite is specified there is no transition to a final halt state. It is nutty to require a simulating termination analyzer to simulate a non-terminating input forever. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer