Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Simulating termination analyzers by dummies --- What does halting
 mean?
Date: Wed, 19 Jun 2024 09:05:29 -0500
Organization: A noiseless patient Spider
Lines: 120
Message-ID: <v4uoj9$1vpm0$10@dont-email.me>
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> <v4u8cu$1o15$1@news.muc.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 19 Jun 2024 16:05:29 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c0498080d6b8a2710b4ab7de903a0762";
	logging-data="2090688"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19qWYuzTwKnk494DZEh/bsv"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:uDIA1xIMWiD9GyoKOibou+3ye8M=
Content-Language: en-US
In-Reply-To: <v4u8cu$1o15$1@news.muc.de>
Bytes: 5833

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