Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: DD emulated by HHH cannot possibly terminate normally --- x86
 code
Date: Sun, 2 Mar 2025 09:11:35 +0100
Organization: A noiseless patient Spider
Lines: 74
Message-ID: <vq13rp$mesl$1@dont-email.me>
References: <vptlfu$3st19$9@dont-email.me>
 <d128909f1359b48293dd1823d22d671435d5640c@i2pn2.org>
 <vpv6ad$8sdm$1@dont-email.me> <vpv9o6$8k7n$1@dont-email.me>
 <vpvcta$a44l$1@dont-email.me> <vpvpvd$cc26$1@dont-email.me>
 <vpvt55$bjn9$14@dont-email.me> <vq02ad$dsct$1@dont-email.me>
 <vq09kr$f3k3$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 02 Mar 2025 09:11:37 +0100 (CET)
Injection-Info: dont-email.me; posting-host="2c4e3ccf99657293cc6a8efcc8948d8f";
	logging-data="736149"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/YK7Hyjz0oeI8hyJWCH2pc"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:QZNonDiflI27srG9tqz7Hp/lmsE=
Content-Language: nl, en-GB
In-Reply-To: <vq09kr$f3k3$2@dont-email.me>

Op 02.mrt.2025 om 01:44 schreef olcott:
> On 3/1/2025 4:39 PM, Fred. Zwarts wrote:
>> Op 01.mrt.2025 om 22:11 schreef olcott:
>>> On 3/1/2025 2:16 PM, Fred. Zwarts wrote:
>>>> Op 01.mrt.2025 om 17:33 schreef olcott:
>>>>> On 3/1/2025 9:39 AM, Fred. Zwarts wrote:
>>>>>> Op 01.mrt.2025 om 15:41 schreef olcott:
>>>>>>> On 3/1/2025 6:49 AM, Richard Damon wrote:
>>>>>>>> On 2/28/25 7:47 PM, olcott wrote:
>>>>>>>>> _DD()
>>>>>>>>> [00002133] 55         push ebp      ; housekeeping
>>>>>>>>> [00002134] 8bec       mov ebp,esp   ; housekeeping
>>>>>>>>> [00002136] 51         push ecx      ; make space for local
>>>>>>>>> [00002137] 6833210000 push 00002133 ; push DD
>>>>>>>>> [0000213c] e882f4ffff call 000015c3 ; call HHH(DD)
>>>>>>>>> [00002141] 83c404     add esp,+04
>>>>>>>>> [00002144] 8945fc     mov [ebp-04],eax
>>>>>>>>> [00002147] 837dfc00   cmp dword [ebp-04],+00
>>>>>>>>> [0000214b] 7402       jz 0000214f
>>>>>>>>> [0000214d] ebfe       jmp 0000214d
>>>>>>>>> [0000214f] 8b45fc     mov eax,[ebp-04]
>>>>>>>>> [00002152] 8be5       mov esp,ebp
>>>>>>>>> [00002154] 5d         pop ebp
>>>>>>>>> [00002155] c3         ret
>>>>>>>>> Size in bytes:(0035) [00002155]
>>>>>>>>>
>>>>>>>>> When we hypothesize that the code at machine address
>>>>>>>>> 0000213c is an x86 emulator then we know that DD
>>>>>>>>> remains stuck in recursive emulation and cannot possibly
>>>>>>>>> reach its own "ret" instruction and terminate normally.
>>>>>>>>>
>>>>>>>>> When we add the additional complexity that HHH also
>>>>>>>>> aborts this sequence at some point then every level
>>>>>>>>> of recursive emulation immediately stops. This does
>>>>>>>>> not enable any DD to ever reach its "ret" instruction.
>>>>>>>>>
>>>>>>>>
>>>>>>>> But then you just negated your first assumption, as a partial 
>>>>>>>> emulator that aborts its emulation, then DD no longer gets stuck.
>>>>>>>>
>>>>>>>
>>>>>>> Cannot possibly reach its own "ret" instruction and terminate 
>>>>>>> normally
>>>>>> proves failure of HHH to reach the end of a proven terminating 
>>>>>> program.
>>>>>
>>>>> DD emulated by HHH according to the above x86 machine code of DD
>>>>> cannot possibly reach its own "ret" instruction and terminate normally
>>>>
>>>>
>>>> In other words, 
>>>
>>> The DD input to HHH unequivocally specifies a
>>> non terminating computation.
>>>
>>>
>>
>> What is the meaning of 'non terminating computation'? 
> 
> The finite string input DD to HHH emulated by HHH according
> to the behavior that it species (which includes pathological
> self-reference) cannot possibly reach its "ret" instruction
> and terminate normally.
> 
In other words a 'non termination computation' as reported by HHH is a 
computation that HHH cannot simulate up to the end, although the direct 
execution and the simulation by other simulators do reach the end of the 
computation described by the same finite string.

Conclusion: Olcott has proven that he can create a simulator that is 
able to report that it cannot reach the end of a simulation, where the 
direct execution and other simulators do reach the end of the same 
program described in the same finite string as given to HHH as input.
Let's admit this result, so that he can have some peaceful time.