Re: Halting Problem: What Constitutes Pathological Input

On 5/7/2025 10:00 PM, Mike Terry wrote:

On 08/05/2025 00:01, olcott wrote:

On 5/7/2025 5:06 PM, Mike Terry wrote:

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

>
The two calls to HHH(DD) are in the part you ignored.
>
HHH1(DD) emulates DD that calls the emulated HHH(DD)
to emulate DD that calls HHH(DD) that emulates itself
emulating DD.
>
I marked these calls with comments.

>
As I explained, it would be clearer if you just supply the requested trace.
>
Are you unable/unwilling to do that?
>

>
*This is the HHH(DD) trace*
>
  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] e823f4ffff     call 000015ee // call HHH
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 // calls HHH
New slave_stack at:14e33e
[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
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>
[000021cb][00103872][00000000] 83c404         add esp,+04
[000021ce][0010386e][00000000] 50             push eax
[000021cf][0010386a][0000075f] 685f070000     push 0000075f
[000021d4][0010386a][0000075f] e8a5e5ffff     call 0000077e
Input_Halts = 0
[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(11427) == 171 Pages
>
*Here is the HHH1(DD) trace again*
This inlcudes the HHH(DD) trace because DD calls HHH(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] e823f4ffff     call 000015ee // call HHH
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 // calls HHH
New slave_stack at:14e33e
[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
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>
[000021cb][00103872][00000000] 83c404         add esp,+04
[000021ce][0010386e][00000000] 50             push eax
[000021cf][0010386a][0000075f] 685f070000     push 0000075f
[000021d4][0010386a][0000075f] e8a5e5ffff     call 0000077e
Input_Halts = 0
[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(11427) == 171 Pages
>

 Thanks for that.
 Can you see from the very traces you've posted that what I and DBush earlier said is exactly right? That makes nonsense of your claims that what was said was "counter-factual".
 It's all there in the traces.  I'll be posting full details in a new thread...
 Regards,
Mike.
 

It is NOT true that the first difference in the behavior
is when HHH aborts its emulation of DD.
The difference in the behavior begins long before that.
It begins as soon as the the DD emulated by HHH1 calls
HHH(DD) and the DD emulated by HHH calls HHH(DD).
The first of these calls DOES return.
as proven by the execution trace.
The second of these calls cannot possibly return.
as proven by repeating sequence in the execution trace.
HHH1 never emulates itself emulating DD because the
call from DD to HHH(DD) returns.
HHH continues to emulate itself emulating DD proving
a different sequence than DD emulated by HHH1. The
call from the emulated DD to HHH(DD) cannot possibly
return.
This is really only a variation of the same idea
as infinite recursion between two functions. The
only difference here is that one of these functions
has the power to stop it.
This causes the other function to stop running yet
not halt because halting is reserved for reaching a
final halt state.
--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer