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: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Wed, 7 May 2025 22:20:59 +0100
Organization: A noiseless patient Spider
Lines: 308
Message-ID: <vvgirs$18j74$1@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvat0g$vtiu$1@dont-email.me>
 <vvatf3$o4v0$3@dont-email.me> <vvaut0$vtiu$4@dont-email.me>
 <vvav6o$o4v0$4@dont-email.me> <vvb329$15u5b$1@dont-email.me>
 <vvb37g$1451r$1@dont-email.me> <vvb43f$15u5b$4@dont-email.me>
 <vvb4ok$o4v0$9@dont-email.me> <vvb52g$15u5b$6@dont-email.me>
 <vvb5ca$o4v0$10@dont-email.me> <vvb5vp$15u5b$7@dont-email.me>
 <vvb675$o4v0$11@dont-email.me> <vvb9d7$1av94$3@dont-email.me>
 <vvbani$1b6l1$1@dont-email.me> <vvbb6s$1av94$4@dont-email.me>
 <vvbcb3$1b6l1$2@dont-email.me> <vvbe0j$1av94$8@dont-email.me>
 <vvbecc$1b6l1$6@dont-email.me> <vvbhk0$1ijna$1@dont-email.me>
 <vvc7t9$29pp8$1@dont-email.me> <vvc86c$2a4cs$1@dont-email.me>
 <vvcufi$2sk4a$3@dont-email.me> <vvdlff$3i09b$2@dont-email.me>
 <vvdo96$3lapa$1@dont-email.me> <vvdr87$3n3t4$1@dont-email.me>
 <vve3mf$3vva3$1@dont-email.me> <vve4ut$f5c$1@dont-email.me>
 <vvehuu$g8eg$1@dont-email.me> <vvej0u$g8jo$1@dont-email.me>
 <vvfv4c$13nqj$1@dont-email.me> <vvg1id$14bdu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 07 May 2025 23:21:01 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d2705041d1026a08b93db71d354a828f";
	logging-data="1330404"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/qATSfpIXQYei9qG+9p8CWVkQAPXv5nkI="
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:6+pgUPjItmnb1zOGxLxMjd6Wklc=
In-Reply-To: <vvg1id$14bdu$1@dont-email.me>
Bytes: 15543

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


> 
>> At this point, no need to be too formal, just a high level trace, e.g. referencing C code rather 
>> than instruction addresses...
>>
> 
========== REMAINDER OF ARTICLE TRUNCATED ==========