Re: How do simulating termination analyzers work? ---Truth Maker Maximalism FULL_TRACE

Op 17.jul.2025 om 15:47 schreef olcott:

On 7/17/2025 3:29 AM, Fred. Zwarts wrote:

Op 16.jul.2025 om 19:49 schreef olcott:

>
_DDD()
[00002192] 55             push ebp
[00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192  // push DDD
[0000219a] e833f4ffff     call 000015d2  // call HHH
[0000219f] 83c404         add esp,+04
[000021a2] 5d             pop ebp
[000021a3] c3             ret
Size in bytes:(0018) [000021a3]
>
Each element of the infinite set of functions
at machine address 000015d2 that emulates 0 to ∞
instructions of the above machine code never
reaches its emulated "ret" instruction final
halt state BECAUSE DDD CALLS EACH EMULATOR IN
RECURSIVE EMULATION.

 

And because HHH would simulate DDD in recursive simulation.
HHH cooperates with DDD to create a recursion. Without HHH starting a new simulation, there would not be a recursion.

The input to HHH(DDD) specifies recursive emulation.

Only because HHH performs a recursive simulation. But, the input specifies a finite recursion, because DDD calls an aborting HHH that returns the value 0.

 

This is already evidence that simulation is not the right tool to analyse the input.
>

 In other words you disagree that a simulation by a UTM
is a correct measure of behavior. (A simulation by a UTM
is defined to be a correct measure of behavior).

Apparently you have a problem with reading.
An UTM can be used to determine halting behaviour only if it completes and reaches the final halt state. It can determine halting behaviour, but it cannot detect non-halting behaviour. If an UTM does not reach the final halt state, we need other means to determine the halting behaviour.

 

But HHH does abort. So, there is no infinite recursion. So, there is a final halt state. But the abort does not help to reach that final halt state. HHH still fails to reach it.

Further only irrelevant repeated claims without evidence:

 _DDD()
[00002192] 55             push ebp
[00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192  // push DDD
[0000219a] e833f4ffff     call 000015d2  // call HHH
[0000219f] 83c404         add esp,+04
[000021a2] 5d             pop ebp
[000021a3] c3             ret
Size in bytes:(0018) [000021a3]

You have been corrected many times that these 18 bytes cannot be the full input. The call at 0000219a refers to an address 000015d2 outside this region. The input for a simulator includes DDD and all functions called by it, directly or indirectly, in this case including the HHH, of which you claim that it returns a value 0. Using this fact, we see that a correct simulation, following the semantics of the x86 language, will continue at 0000219f with this value and reach the final halt state at 000021a3.
That HHH cannot reach that final halt state is a failure of HHH: it cannot do a correct simulation up to the end.

 Each element of the infinite set of functions
at machine address 000015d2 that emulates 0 to ∞
instructions of the above machine code never
reaches its emulated "ret" instruction final
halt state BECAUSE DDD CALLS EACH EMULATOR IN
RECURSIVE EMULATION.

Irrelevant, because there is only a finite recursion for aborting simulators.
Yes, all aborting simulators fail to reach the final halt state, illustrating the fact that for any input that includes HHH, HHH is not the correct tool to analyse the behaviour specified in the input.

 *ChatGPT agrees and provides the reasoning why it agrees*
https://chatgpt.com/share/6877f09c-7b18-8011-b075-ea3671e57886
 

This illustrates that simulation is not the right tool for this input.

 Disagreeing with the definition of a UTM is incorrect.

But applying the definition of an UTM to an aborting simulator is not honest. An aborting simulator is not a pure UTM.

 

Each element in the infinite set fails to reach the final halt state.

 Because it remains stuck in recursive emulation.
 void Infinite_Recursion()
{
   Infinite_Recursion();
   return;
}
 Infinite_Recursion() correctly simulated bu HHH also
cannot possibly reach its own simulated "return"
statement final halt state. Not possibly reaching
final halt state is the correct measure on non-halting
for both HHH(Infinite_Recursion) and HHH(DDD).

But aborting at some point is not a sufficient proof for non-termination. Other logic is needed to prove non-termination.
void Finite_Recursion (int N) {
   if (N > 0) Finite_Recursion (N - 1);
   printf ("Olcott thinks this is never printed.\n");
}
When HHH would conclude that there is non-termination behaviour, because it sees recursion, it is in error.
So, it is important to see the difference between finite recursion and infinite recursion. In the case of DDD based on an aborting HHH, there is only a finite recursion. Even if HHH cannot see that, the specification of a halting program does not change.

 

There is a final halt state for each of them, but the all fail to reach it. (Of course the very different HHH that does not abort at all, has no final halt state, so it fails as well.)