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

On 6/19/2024 4:29 AM, Alan Mackenzie wrote:

olcott <polcott333@gmail.com> wrote:

On 6/18/2024 4:36 PM, Alan Mackenzie wrote:

[ Followup-To: set ]

 

In comp.theory olcott <polcott333@gmail.com> wrote:

On 6/18/2024 12:57 PM, joes wrote:

Am Tue, 18 Jun 2024 12:25:44 -0500 schrieb 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.

 

So H0 returns "doesn't halt" to DDD, which then stops running,
so H0 should have returned "halts".

 

This was three messages ago.
I had to make sure that you understood that halting
does not mean stopping for any reason and only includes
the equivalent of terminating normally.

 

No.  You're wrong, here.  A turing machine is either running or it's
halted.  There's no third alternative.  If your C programs are not in one
of these two states, they're not equivalent to turing machines.

 

Although I agree with this there seems to be nuances of
disagreement across the experts.

 I doubt that very much.  The whole point of turing machines is to remove
ambiguity and unneeded features from the theory of computation.  A third
alternative state is unneeded.
 

Some people say that a TM can halt in a non-final state.

DDD correctly emulated by H0 DOES NOT TERMINATE NORMALLY.

 

There is no concept of "normal" termination in a turing machine.  The
thing is either running or it's halted.

 

I develop one within the conventional notions below.

 You don't need it.  You just confuse yourself (and possibly others) with
it.  What you call the "aborted state" is just one more final state for
the TM to halt in.
 

When the adapted UTM halts after simulating ten state transitions
of a Turing Machine Description that only loops we cannot correctly
say that the looping input has halted.
When the adapted UTM halts after recognizing the repeating state
of a Turing Machine Description that only loops and transitions to
its reject state then this adapted UTM is a halt decider for
inputs that only loop.

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.

Some TMs do not loop and do not halt.

 

A UTM can be adapted so that it only simulates a fixed number of
iterations of an input that loops.

 

As has often been said, it is then no longer a universal turing machine.

 

So what?

 

None-the-less it does derive the notion of abnormal termination
as applied to Turing Machines.

 As I said, that is not a useful notion.  It just confuses.
 

It is a perfectly useful notion as I have defined above
because the adapted UTM becomes a halt decider for inputs
that only loop.

When this UTM stops simulating this Turing machine description we
cannot correctly say that this looping input halted.

 

Yes, we can.  It has been designed to count to 42 then halt.  It is then
in the halted state.

 

Two different machines.
(a) The TM description of a looping machine.
(b) A UTM that has been adapted to count to five repeating
states before it aborts its simulation of the looping machine.

 (b) is not a universal turing machine.  It is a TM, one of whose halting
states is having counted five repeating states.
 

Yes. We also cannot say that that input was simulated correctly.

 

Indeed, not.

 

It is a mistake for a simulating termination analyzer
to simulate infinite repeating states.

 How can that be a "mistake" if it's what the thing is programmed to do?
 

Termination analyzers are required to halt so it fails
to meet its spec.

-- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

 

--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer