Re: Halting Problem: What Constitutes Pathological Input

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.
 <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
     If simulating halt decider H correctly simulates its
     input D until H correctly determines that its simulated D
     *would never stop running unless aborted* then
      *input D* refers to the actual HHH/DD pair

..which is not to be changed during hypothetical modifications to H

      *would never stop running unless aborted*
      refers to the hypothetical HHH/DD pair where
      HHH and DDD are exactly the same except that
      this hypothetical HHH does not abort the
      simulation of its input.

No, that doesn't work in your x86utm because you mix up code (HHH) and data (DD, which directly calls HHH).  DD must be "exactly the same" /including all its subroutines/, but DD calls HHH so HHH must be exactly the same, otherwise the input has been changed which is NOT ALLOWED.
To make this work you have to create a /new/ "HHH that does not abort the simulation".  E.g. clone HHH to HHH_hypothetical then take out the abort logic from HHH_hypothetical.  From main() call HHH_hypothetical(DD).  That way DD is unchanged as required.

 

The trace by UTM continued further, with DD returning some time later.
>

 The above HHH1(DD) is this UTM.

HHH1 will serve in this case, since it happens to not abort due to your coding errors.  It would be cleaner to make a function UTM() which just has the DebugStep loop and no abort logic.
So... are you saying that HHH has seen enough of the simulation to correctly determined that HHH1(DD) never returns?  That would be bizarre, since you know HHH1(DD) /does/ return.

 The DD correctly emulated by HHH cannot possibly return.
Not even after an infinite number of steps of correct emulation.

I explained in an earlier post why that is duffer-speak, and suggested sensible alternative wordings.  You're welcome.
Mike.