Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Simulating termination analyzers by dummies --- What does halting
 mean?
Date: Wed, 19 Jun 2024 11:10:40 -0500
Organization: A noiseless patient Spider
Lines: 116
Message-ID: <v4uvu0$21os1$4@dont-email.me>
References: <v4oaqu$f9p5$1@dont-email.me> <v4os9e$i70m$1@dont-email.me>
 <v4p9mb$lavj$1@dont-email.me> <v4qe53$a0nm$1@i2pn2.org>
 <v4qn65$10qh6$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> <v4u48g$1rrod$3@dont-email.me>
 <v4ulde$1vpm0$3@dont-email.me> <v4uou1$1vtc8$3@dont-email.me>
 <v4us79$21810$3@dont-email.me> <v4uuor$1vtc8$6@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 19 Jun 2024 18:10:41 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c0498080d6b8a2710b4ab7de903a0762";
	logging-data="2155393"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19jfy5KaAOvszSVuJ1aRo9W"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ppMJgKV9XPsgcH6ybrCQtayvRCI=
In-Reply-To: <v4uuor$1vtc8$6@dont-email.me>
Content-Language: en-US
Bytes: 5978

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