Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mike Terry Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Wed, 7 May 2025 23:06:10 +0100 Organization: A noiseless patient Spider Lines: 187 Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 08 May 2025 00:06:11 +0200 (CEST) Injection-Info: dont-email.me; posting-host="69c073830ae6b666c3dcb0619ca095de"; logging-data="1338482"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/OUJX8+qM9OLEJ8bRDRm7pHU+2bOcOwVc=" User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.18.2 Cancel-Lock: sha1:oK3rhznfqTXluE8E6iHS5qSuo+A= In-Reply-To: On 07/05/2025 22:32, olcott wrote: > On 5/7/2025 4:20 PM, Mike Terry wrote: >> On 07/05/2025 17:25, olcott wrote: >>> On 5/7/2025 10:44 AM, Mike Terry wrote: >>>> On 07/05/2025 04:11, olcott wrote: >>>>> On 5/6/2025 9:53 PM, Mike Terry wrote: >>>>>> On 07/05/2025 00:11, olcott wrote: >>>>>>> On 5/6/2025 5:49 PM, Mike Terry wrote: >>>>>>>> On 06/05/2025 21:25, olcott wrote: >>>>>>>>> On 5/6/2025 2:35 PM, dbush wrote: >>>>>>>>>> On 5/6/2025 2:47 PM, olcott wrote: >>>>>>>>>>> On 5/6/2025 7:14 AM, dbush wrote: >>>>>>>>>>>> On 5/6/2025 1:54 AM, olcott wrote: >>>>>>>>>>>>> On 5/6/2025 12:49 AM, Richard Heathfield wrote: >>>>>>>>>>>>>> On 06/05/2025 00:29, olcott wrote: >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> It is the problem incorrect specification that creates >>>>>>>>>>>>>>> the contradiction. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Not at all. The contradiction arises from the fact that it is not possible to >>>>>>>>>>>>>> construct a universal decider. >>>>>>>>>>>>>> >>>>>>>>>>>>>>> Everyone here insists that functions computed >>>>>>>>>>>>>>> by models of computation can ignore inputs and >>>>>>>>>>>>>>> base their output on something else. >>>>>>>>>>>>>> >>>>>>>>>>>>>> I don't think anyone's saying that. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Maybe you don't read so well. >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> What are the exact steps for DD to be emulated by HHH >>>>>>>>>>>>> according to the semantics of the x86 language? >>>>>>>>>>>>> *Only an execution trace will do* >>>>>>>>>>>> >>>>>>>>>>>> The exact same steps for DD to be emulated by UTM. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> _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] >>>>>>>>>>> >>>>>>>>>>> Machine address by machine address specifics >>>>>>>>>>> that you know that you cannot provide because >>>>>>>>>>> you know that you are wrong. >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> HHH and UTM emulate DD exactly the same up until the point that HHH aborts, >>>>>>>>> >>>>>>>>> When you trace through the actual steps you >>>>>>>>> will see that this is counter-factual. >>>>>>>> >>>>>>>> No, it is exactly right. Remember, I posted a comparison of the two traces side by side >>>>>>>> some time ago, and they were indeed IDENTICAL line for line up to the point where HHH >>>>>>>> decided to discontinue simulating. >>>>>>> >>>>>>> That is counter-factual. >>>>>> >>>>>> Dude! :/ I posted the comparison and the traces were the same up to the point where HHH >>>>>> discontinued the simulation. How can it be "counter-factual"? >>>>>> >>>>> >>>>> HHH1(DD) the call from DD to HHH(DD) returns. >>>>> HHH(DD) the call from DD to HHH(DD) cannot possibly return. >>>>> >>>>> A call that returns and a call that cannot possibly >>>>> return *are not exactly the same thing* >>>> >>>> You need to read what posters actually say. I said the traces were the same up to the point >>>> where HHH stops simulating. >>> >>> THAT IS COUNTER-FACTUAL. >>> HHH continues to emulate DD long after their paths diverge. >>> >>> HHH1 only emulates DD once. >>> HHH emulates DD once and then emulates itself emulating DD. >>> >>>> I didn't say anything about calls that return or do not return "being the same thing" and none >>>> of what you relates to whether what I said was correct. >>>> >>>> Look, if you insist the traces are not the same up to the point where HHH stops simulating, show >>>> the two traces and we'll just look and see! Simples. >>>> >>> >>> HHH1(DD) emulates DD once. >>> HHH(DD) emulates DD once and then emulates itself emulating DD. >>> >>> 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][0000213e] 683e210000 push 0000213e // push DD >>> [000021c6][0010386a][000021cb] e853f3ffff call 0000151e // call HHH1 >>> New slave_stack at:103916 >>> >>> Begin Local Halt Decider Simulation Execution Trace Stored at:11391e >>> [0000213e][0011390e][00113912] 55 push ebp >>> [0000213f][0011390e][00113912] 8bec mov ebp,esp >>> [00002141][0011390a][00103916] 51 push ecx >>> [00002142][00113906][0000213e] 683e210000 push 0000213e // push DD >>> [00002147][00113902][0000214c] e8a2f4ffff call 000015ee // call HHH >>> New slave_stack at:14e33e >>> >>> Begin Local Halt Decider Simulation Execution Trace Stored at:15e346 >>> [0000213e][0015e336][0015e33a] 55 push ebp >>> [0000213f][0015e336][0015e33a] 8bec mov ebp,esp >>> [00002141][0015e332][0014e33e] 51 push ecx >>> [00002142][0015e32e][0000213e] 683e210000 push 0000213e // push DD >>> [00002147][0015e32a][0000214c] e8a2f4ffff call 000015ee // call HHH >>> New slave_stack at:198d66 >>> [0000213e][001a8d5e][001a8d62] 55 push ebp >>> [0000213f][001a8d5e][001a8d62] 8bec mov ebp,esp >>> [00002141][001a8d5a][00198d66] 51 push ecx >>> [00002142][001a8d56][0000213e] 683e210000 push 0000213e >>> [00002147][001a8d52][0000214c] e8a2f4ffff call 000015ee >>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped >>> >>> [0000214c][0011390a][00103916] 83c404 add esp,+04 >>> [0000214f][0011390a][00000000] 8945fc mov [ebp-04],eax >>> [00002152][0011390a][00000000] 837dfc00 cmp dword [ebp-04],+00 >>> [00002156][0011390a][00000000] 7402 jz 0000215a >>> [0000215a][0011390a][00000000] 8b45fc mov eax,[ebp-04] >>> [0000215d][0011390e][00113912] 8be5 mov esp,ebp >>> [0000215f][00113912][000015d3] 5d pop ebp >>> [00002160][00113916][0003a980] c3 ret >>> [000021cb][00103872][00000000] 83c404 add esp,+04 >>> [000021ce][0010386e][00000001] 50 push eax >>> [000021cf][0010386a][0000075f] 685f070000 push 0000075f >>> [000021d4][0010386a][0000075f] e8a5e5ffff call 0000077e >>> Input_Halts = 1 >>> [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(400885) == 5983 Pages >> >> Excellent - above we have the trace for HHH1, half of what we need. While we /could/ use that to >> /deduce/ what the trace for HHH should be, we shouldn't have to resort to that. The clean way to >> proceed is for you to now post the similar trace for main calling HHH, then we can compare them >> with minimal editing... >> >> Mike. >> >> > > The two calls to HHH(DD) are in the part you ignored. > > HHH1(DD) emulates DD that calls the emulated HHH(DD) ========== REMAINDER OF ARTICLE TRUNCATED ==========