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

Am Thu, 20 Jun 2024 09:16:32 -0500 schrieb olcott:

On 6/20/2024 3:23 AM, Fred. Zwarts wrote:

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

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 halts iff H0 halts.

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.

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.

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 DDD()
{
   H0(DDD);
}
int main()
{
   H0(DDD);
}
>
Every C programmer that knows what an x86 emulator is knows that
when H0 emulates the machine language of
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*
[blah blah Sipser]

 
It seems you never learn. There is no correct simulation,
so Sipser words do not apply.

Either not paying attention or deliberately deceptive.

*H correctly simulates its input D*
*until H correctly determines that its simulated D*

whence it stops simulating (correctly, or at all)

*would never stop running unless aborted then*

stops simulating the following steps.

*This is simulating a finite number of steps of a non-terminating input*

I.e. not a full simulation.

--
Man kann mit dunklen Zahlen nicht rechnen. Für die eigentliche Mathematik
sind sie vollkommen nutzlos. --Wolfgang Mückenheim