Re: Simulating termination analyzers by dummies --- What does halting mean?

On 6/19/2024 10:50 AM, Fred. Zwarts wrote:

Op 19.jun.2024 om 17:07 schreef olcott:

On 6/19/2024 9:11 AM, Fred. Zwarts wrote:

Op 19.jun.2024 om 15:11 schreef olcott:

On 6/19/2024 3:18 AM, Fred. Zwarts wrote:

Op 18.jun.2024 om 19:25 schreef olcott:

On 6/18/2024 12:06 PM, joes wrote:
>
void DDD()
{
   H0(DDD);
}
>
DDD correctly simulated by any H0 cannot possibly halt.
>

DDD halts iff H0 halts.

>
Halting is a technical term-of-the-art that corresponds
to terminates normally. Because Turing machines are
abstract mathematical objects there has been no notion
of abnormal termination for a Turing machine.
>
We can derive a notion of abnormal termination for Turing
machines from the standard terms-of-the-art.
>
Some TM's loop and thus never stop running, this is classical
non-halting behavior. UTM's simulate Turing machine descriptions.
This is the same thing as an interpreter interpreting the
source-code of a program.
>
A UTM can be adapted so that it only simulates a fixed number
of iterations of an input that loops. When this UTM stops
simulating this Turing machine description we cannot correctly
say that this looping input halted.
>

>
If the code specifies 5 iterations and the simulator simulates only 3 iterations, it is incorrect to conclude that the repetition show non-halting behaviour.

>
It is correct do say that the simulated input did not terminate
normally, thus defining the notion of abnormal termination
within Turing machines.
>

Similarly, when your H, H0, or other H simulates itself, its simulation aborts one cycle too early and therefore the non-halting conclusion is incorrect.

>
I was confused bout this for three days four years ago and then I
got over it. No simulating termination analyzer can wait for an
inner instance of itself to abort the simulation or it waits forever.
>
Whenever the outer directly executed simulating termination analyzer
waits for any fixed number of repeating states it remains permanently
ahead of the next inner instance by exactly one repeating state. If
this is going to be permanently over your head then we need to stop
talking.

>
No, I understand it perfectly, but it seems to be over your head. We agree that H needs to stop to prevent infinite recursion, but it is over your head to see that when it stops, it misses the part of itself where its simulation also stops, one repeating state further. So, the non-halting conclusion is wrong, because the abort is premature.

>
typedef void (*ptr)();
int H0(ptr P);
>
void Infinite_Loop()
{
   HERE: goto HERE;
}
>
void Infinite_Recursion()
{
   Infinite_Recursion();
}
>
void DDD()
{
   H0(DDD);
}
>
int main()
{
   H0(Infinite_Loop);
   H0(Infinite_Recursion);
   H0(DDD);
}
>
Every C programmer that knows what an x86 emulator is knows that when
H0 emulates the machine language of Infinite_Loop, Infinite_Recursion,
and DDD that it must abort these emulations so that itself can terminate
normally.

 That might be true, but every competent C programmer also knows that such an abort would cause an incorrect simulation.

*Not at all*
Introduction to the Theory of Computation, by Michael Sipser
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/
<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
   H can abort its simulation of D and correctly report that D
   specifies a non-halting sequence of configurations.
</MIT Professor Sipser agreed to ONLY these verbatim words10/13/2022>
--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer