Re: Halting Problem: What Constitutes Pathological Input

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

 The directed graph of the x86 code leaves zero
room for incorrect interpretation.
 

>

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/,

>
Not at all. Professor Sipser agreed that the actual
HHH/DD must base its decision on the hypothetical
HHH/DD that never aborts its simulation.

>
Nonsense.  He is taking it as read that the input is not changed.  What he agreed was that the actual HHH can base its decision on the hypothetical HHH that never aborts its simulation, running against *identical input* DD.  Identical means has identical behaviour to original DD, in particular it calls original HHH,

 No it does not.
*simulated D would never stop running unless aborted*
refers to a hypothetical HHH that does not abort.
 

not some modified HHH or UTM.
>
Of course, Sipser would not understand how you have mangled the design of your utmx86 environment. He would naturally take it that you were correctly implementing basic features of the TM halting problem, like the input data being totally distinct from the TM state table.  So it would simply never occur to him that in your world, changing the code of HHH would have any effect on the data input DD, which explains why he does not explicitly mention that.
>

>
*would never stop running unless aborted*
*would never stop running unless aborted*
*would never stop running unless aborted*

yawn
>

>

but DD calls HHH so HHH must be exactly the same, otherwise the input has been changed which is NOT ALLOWED.
>

>
Intuitively it would seem that way until you examine
every single detail 100% completely.
>

To make this work you have to create a /new/ "HHH that does not abort the simulation".

>
Professor Sipser already agreed that the actual HHH/DD
must base its decision on the hypothetical HHH/DD
that never aborts.

>
You are quite incapable of understanding what Sipser was agreeing to.

 *simulated D would never stop running unless aborted*
doesn't really leave much subjective leeway of interpretation.
 This can only mean the behavior of DD when a hypothetical
HHH that never aborts would replace the body of the actual HHH.
 

More generally you have a problem understanding what other people believe and what they are communicating to you.  I've suggested you have some neural wiring issue, and for sure this would be tied in to that somehow.
>

 No it is all a matter of people not bothering to pay
enough attention because of their mental bias that
I must be wrong.
 

Regardless of that, you are trying to use Sipser's quote as an appeal to authority, which you understand is a fallacy but think its ok to do it anyway.  [Even though you are quick to accuse other people of doing that when it suits you.]
>

 An appeal to a qualified authority is inductively sound.
 

Just stop mentioning Sipser's quote altogether!  It is not helping your case in any shape or form.
>

>

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 does not happen to not abort due to coding
errors. That is a reckless disregard for the truth.
The code has specified exactly why it need not
abort for several years now.

>
No, it's due to coding errors.  You intended HHH1 to be a clone of HHH, with the same algorithm as HHH, but at a different address.

 

You just screwed it up due to your inappropriate use of global variables.  If you had coded things correctly HHH(DD) and HHH1(DD) would both have (incorrectly) decided halts.  I explained the gory details of all this to you months/years ago.
>

 Merely proving that you still fail to understand
that the fact that DD calls HHH(DD) and does not call
HHH1(DD) MAKES ALL THE DIFFERENCE IN THEIR BEHAVIOR.
 

>

 It would be cleaner to make a function UTM() which just has the DebugStep loop and no abort logic.
>

>
Professor Sipser already agreed that the actual HHH/DD
must base its decision on the hypothetical HHH/DD
that never aborts, AKA your UTM.

>
Sipser would be ok with my UTM, simulating THE ORIGINAL DD, which calls THE ORIGINAL HHH.
>

 The words that he agreed to
*simulated D would never stop running unless aborted*
 Since this HHH DOES ABORT the HHH THAT DOES NOT ABORT
must be a different hypothetical HHH.
 Simulating halt deciders must PREDICT WHAT THE BEHAVIOR
WOULD BE IF THEY DID NOT ABORT.
 They cannot simply wait-and-see or they get stuck.