| Deutsch English Français Italiano |
|
<vf1stu$8h0v$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott <polcott333@gmail.com> Newsgroups: comp.theory Subject: I have always been correct about emulating termination analyzers --- PROOF Date: Sat, 19 Oct 2024 22:20:30 -0500 Organization: A noiseless patient Spider Lines: 260 Message-ID: <vf1stu$8h0v$1@dont-email.me> 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> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 20 Oct 2024 05:20:31 +0200 (CEST) Injection-Info: dont-email.me; posting-host="77a46f28b4cad16507a67d9d8c01a608"; logging-data="279583"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/pAnJYFs1rLqJ5+jkkehfV" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:myM1/XY/mbJBkCeMr3ZKqVYe8Dc= In-Reply-To: <dedb2801cc230a4cf689802934c4b841ae1a29eb@i2pn2.org> X-Antivirus-Status: Clean X-Antivirus: Norton (VPS 241019-8, 10/19/2024), Outbound message Content-Language: en-US Bytes: 12452 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 >>>>>> even if it just guesses. >>>>>> >>>>>>> Also, we can make a trivial HHH, that just does the absolute ========== REMAINDER OF ARTICLE TRUNCATED ==========