Path: ...!news-out.netnews.com!s1-1.netnews.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!nntp.club.cc.cmu.edu!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: I have always been correct about emulating termination analyzers
 --- PROOF
Date: Sun, 20 Oct 2024 07:46:38 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <592109c757262c48aaca517a829ea1867913316b@i2pn2.org>
References: <ves6p1$2uoln$1@dont-email.me>
 <3232d8a0cc7b5d4bba46321bf682c94573bf1b7c@i2pn2.org>
 <vesemu$2v7sh$1@dont-email.me>
 <a9fb95eb0ed914d0d9775448c005111eb43f2c5b@i2pn2.org>
 <veslpf$34ogr$1@dont-email.me>
 <647fe917c6bc0cfc78083ccf927fe280acdf2f9d@i2pn2.org>
 <vetq7u$3b8r2$1@dont-email.me>
 <522ecce215e636ddb7c9a1f75bff1ba466604cc5@i2pn2.org>
 <veuvt9$3hnjq$1@dont-email.me>
 <87634d01e18903c744d109aaca3a20b9ce4278bb@i2pn2.org>
 <vev8gg$3me0u$1@dont-email.me>
 <eb38c4aff9c8bc250c49892461ac25bfccfe303f@i2pn2.org>
 <vf051u$3rr97$1@dont-email.me>
 <e3f28689429722f86224d0d736115e4d1895299b@i2pn2.org>
 <vf1hun$39e3$1@dont-email.me>
 <dedb2801cc230a4cf689802934c4b841ae1a29eb@i2pn2.org>
 <vf1stu$8h0v$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 20 Oct 2024 11:46:39 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2876054"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vf1stu$8h0v$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
X-Received-Bytes: 15529
Bytes: 15700
Lines: 334

On 10/19/24 11:20 PM, olcott wrote:
> On 10/19/2024 9:27 PM, Richard Damon wrote:
>> On 10/19/24 8:13 PM, olcott wrote:
>>> On 10/19/2024 4:53 PM, Richard Damon wrote:
>>>> On 10/19/24 7:26 AM, olcott wrote:
>>>>> On 10/19/2024 6:21 AM, Richard Damon wrote:
>>>>>> On 10/18/24 11:19 PM, olcott wrote:
>>>>>>> On 10/18/2024 9:49 PM, Richard Damon wrote:
>>>>>>>> On 10/18/24 8:52 PM, olcott wrote:
>>>>>>>>> On 10/18/2024 6:06 PM, Richard Damon wrote:
>>>>>>>>>> On 10/18/24 10:10 AM, olcott wrote:
>>>>>>>>>>> On 10/18/2024 6:17 AM, Richard Damon wrote:
>>>>>>>>>>>> On 10/17/24 11:47 PM, olcott wrote:
>>>>>>>>>>>>> On 10/17/2024 10:27 PM, Richard Damon wrote:
>>>>>>>>>>>>>> On 10/17/24 9:47 PM, olcott wrote:
>>>>>>>>>>>>>>> On 10/17/2024 8:13 PM, Richard Damon wrote:
>>>>>>>>>>>>>>>> On 10/17/24 7:31 PM, olcott wrote:
>>>>>>>>>>>>>>>>> _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]
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> When DDD is correctly emulated by HHH according
>>>>>>>>>>>>>>>>> to the semantics of the x86 language DDD cannot
>>>>>>>>>>>>>>>>> possibly reach its own machine address [00002183]
>>>>>>>>>>>>>>>>> no matter what HHH does.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> +-->[00002172]-->[00002173]-->[00002175]-->[0000217a]--+
>>>>>>>>>>>>>>>>> +------------------------------------------------------+
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> That may not line up that same way when view
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> https://en.wikipedia.org/wiki/State_diagram
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Except that 0000217a doesn't go to 00002172, but to 
>>>>>>>>>>>>>>>> 000015d2
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> IS THIS OVER YOUR HEAD?
>>>>>>>>>>>>>>> What is the first machine address of DDD that HHH
>>>>>>>>>>>>>>> emulating itself emulating DDD would reach?
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Yes, HHH EMULATES the code at that address, 
>>>>>>>>>>>>>
>>>>>>>>>>>>> Which HHH emulates what code at which address?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Everyone, just once, which you should know, but ignore.
>>>>>>>>>>>>
>>>>>>>>>>>> The Emulating HHH sees those addresses at its begining and 
>>>>>>>>>>>> then never again.
>>>>>>>>>>>>
>>>>>>>>>>>> Then the HHH that it is emulating will see those addresses, 
>>>>>>>>>>>> but not the outer one that is doing that emulation of HHH.
>>>>>>>>>>>>
>>>>>>>>>>>> Then the HHH that the second HHH is emulating will, but 
>>>>>>>>>>>> neither of the outer 2 HHH.
>>>>>>>>>>>>
>>>>>>>>>>>> And so on.
>>>>>>>>>>>>
>>>>>>>>>>>> Which HHH do you think EVER gets back to 00002172?
>>>>>>>>>>>>
>>>>>>>>>>>> What instruction do you think that it emulates that would 
>>>>>>>>>>>> tell it to do so?
>>>>>>>>>>>>
>>>>>>>>>>>> It isn't the call instruction at 0000217a, as that tells it 
>>>>>>>>>>>> to go into HHH.
>>>>>>>>>>>>
>>>>>>>>>>>> At best the trace is:
>>>>>>>>>>>>
>>>>>>>>>>>> 00002172
>>>>>>>>>>>> 00002173
>>>>>>>>>>>> 00002175
>>>>>>>>>>>> 0000217a
>>>>>>>>>>>> conditional emulation of 00002172
>>>>>>>>>>>> conditional emulation of 00002173
>>>>>>>>>>>> conditional emulation of 00002175
>>>>>>>>>>>> conditional emulation of 0000217a
>>>>>>>>>>>> CE of CE of 00002172
>>>>>>>>>>>> ...
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> OK great this is finally good progress.
>>>>>>>>>>>
>>>>>>>>>>>> The "state" never repeats, it is alway a new state, 
>>>>>>>>>>>
>>>>>>>>>>> Every emulated DDD has an identical process state at every point
>>>>>>>>>>> in its emulation trace when adjusting for different top of 
>>>>>>>>>>> stack values.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Nope, remember, each of those levels are CONDITIONAL, 
>>>>>>>>>
>>>>>>>>> *There are THREE different questions here*
>>>>>>>>> (1) Can DDD emulated by HHH according to the semantics
>>>>>>>>>      of the x86 language possibly reach its machine address
>>>>>>>>>      [00002183] no matter what HHH does?
>>>>>>>>>
>>>>>>>>
>>>>>>>> Ambiguouse question, as pointed out previously.
>>>>>>>>
>>>>>>>> A) Do you mean the behavior of the PROGRAM DDD, that HHH has 
>>>>>>>> emulated a copy of.
>>>>>>>>
>>>>>>>> In that case, the answer is, if HHH aborts its emulation and 
>>>>>>>> return, YES, if HHH never aborts its emulation, and thus doesn't 
>>>>>>>> ever return an answer to anyone NO.
>>>>>>>>
>>>>>>>> B) If you mean, does the emulation done by HHH ever reach that 
>>>>>>>> place, no.
>>>>>>>>
>>>>>>>
>>>>>>> We are not asking if the code of HHH reaches inside
>>>>>>> the code of DDD. Of course it doesn't this is stupid.
>>>>>>>
>>>>>>> We are asking does any DDD of any DDD/HHH pair of the
>>>>>>> infinite set of pairs such that DDD is emulated by HHH
>>>>>>> according to the semantics of the x86 language reach its
>>>>>>> own return instruction?
>>>>>>>
>>>>>>>>
>>>>>>>>> (2) Does HHH correctly detect and report the above?
>>>>>>>>
>>>>>>>> No, because that isn't what you claim HHH is doing, so it can't 
>>>>>>>> be correct about that.
>>>>>>>>
>>>>>>>
>>>>>>> In other words you fail to comprehend that DDD failing
>>>>>>> to reach its "return" instruction is isomorphic to:
>>>>>>>
>>>>>>> On 10/14/2022 7:44 PM, Ben Bacarisse wrote:
>>>>>>>  > ... PO really /has/ an H
>>>>>>>  > (it's trivial to do for this one case) that correctly determines
>>>>>>>  > that P(P) *would* never stop running *unless* aborted.
>>>>>>>
>>>>>>>> We need to look at the two possible interpreations to question 1.
>>>>>>>>
>>>>>>>> If you means A, then since HHH says no but the correct answer is 
>>>>>>>> yes, it is wrong.
>>>>>>>>
>>>>>>>> If you mean B, and you mean your question is can HHH predict 
>>>>>>>> that it can't reach the final state, but only needs to be right 
>>>>>>>> for this one input, then the problem is the question has become 
>>>>>>>> trivial, if it doesn't need to actually know anything about the 
>>>>>>>> input, it can just be programmed to say no.
>>>>>>>>
>>>>>>>
>>>>>>> I mean that the execution trace of DDD proves that HHH is correct
>>>>>>> to reject DDD as impossibly reaching its own "return" instruction
========== REMAINDER OF ARTICLE TRUNCATED ==========