Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!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: Tue, 13 May 2025 12:16:51 +0300
Organization: -
Lines: 136
Message-ID: <vvv2m3$1npfk$1@dont-email.me>
References: <vvma0u$34vcu$1@dont-email.me> <vvmvu6$3dt3n$1@dont-email.me> <vvnrkv$3in62$7@dont-email.me> <vvpq4q$446u$1@dont-email.me> <vvqiu1$gldn$8@dont-email.me> <vvs8k1$vr8s$1@dont-email.me> <vvt10i$14pca$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 13 May 2025 11:16:52 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="69576f0644f413b581cc430fda63c863";
	logging-data="1828340"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18h5dAT+PXFiIO2DLvYTK4q"
User-Agent: Unison/2.2
Cancel-Lock: sha1:I4B0GkJ+DdqSwrpqObCcOWaghLo=
Bytes: 7204

On 2025-05-12 14:36:01 +0000, olcott said:

> 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.

True but not applicable to DDD, which is essentially finite if HHH
is a decider and uninteresting if HHH is not a decider.

-- 
Mikko