Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Try and prove that DDD correctly emulated by HHH reaches its final halt state
Date: Sun, 11 May 2025 12:20:26 +0300
Organization: -
Lines: 111
Message-ID: <vvpq4q$446u$1@dont-email.me>
References: <vvma0u$34vcu$1@dont-email.me> <vvmvu6$3dt3n$1@dont-email.me> <vvnrkv$3in62$7@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 11 May 2025 11:20:27 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8a4d2e962e80928203138f924459649c";
	logging-data="135390"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18RC8UPA6G61fgQOQ/FatI2"
User-Agent: Unison/2.2
Cancel-Lock: sha1:YPrNSaTsEF8qPt2pX0UImNnzx8o=

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.

-- 
Mikko