Path: ...!news.mixmin.net!news2.arglkargh.de!news.karotte.org!news.space.net!news.muc.de!.POSTED.news.muc.de!not-for-mail
From: Alan Mackenzie <acm@muc.de>
Newsgroups: comp.theory
Subject: Re: Simulating termination analyzers by dummies --- What does halting mean?
Date: Wed, 19 Jun 2024 09:29:02 -0000 (UTC)
Organization: muc.de e.V.
Message-ID: <v4u8cu$1o15$1@news.muc.de>
References: <v4oaqu$f9p5$1@dont-email.me>   <v4qnkf$a0nm$5@i2pn2.org> <v4qpvo$10qh6$2@dont-email.me> <v4qrmd$a0nm$6@i2pn2.org> <v4qrr8$15beg$1@dont-email.me> <v4qsav$a0nn$3@i2pn2.org> <v4qtaa$15gc5$1@dont-email.me> <v4qu3p$a0nm$7@i2pn2.org> <v4quti$15nn8$1@dont-email.me> <v4rrge$bivn$1@i2pn2.org> <v4s1l0$1boeu$6@dont-email.me> <v4seq5$cbcu$1@i2pn2.org> <v4sfuo$1enie$1@dont-email.me> <v4shpp$cbcu$2@i2pn2.org> <v4st0g$1hjnp$1@dont-email.me> <v4sull$2f03$1@news.muc.de> <v4svmn$1i267$1@dont-email.me>
Injection-Date: Wed, 19 Jun 2024 09:29:02 -0000 (UTC)
Injection-Info: news.muc.de; posting-host="news.muc.de:2001:608:1000::2";
	logging-data="57381"; mail-complaints-to="news-admin@muc.de"
User-Agent: tin/2.6.3-20231224 ("Banff") (FreeBSD/14.0-RELEASE-p5 (amd64))
Bytes: 4563
Lines: 94

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.

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

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


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

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

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

-- 
Alan Mackenzie (Nuremberg, Germany).