Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory,sci.logic
Subject: Re: Simulating termination analyzers by dummies --- What does halting
 mean?
Date: Fri, 21 Jun 2024 10:11:38 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v541mq$lkkb$1@i2pn2.org>
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>
 <v4uvu0$21os1$4@dont-email.me> <v50ot4$2fh9b$1@dont-email.me>
 <v51dk0$2jmrd$2@dont-email.me> <v53bqv$324b5$1@dont-email.me>
 <v53u8h$35vak$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 21 Jun 2024 14:11:38 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="709259"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <v53u8h$35vak$2@dont-email.me>
Content-Language: en-US
Bytes: 9216
Lines: 187

On 6/21/24 9:12 AM, olcott wrote:
> On 6/21/2024 2:58 AM, Fred. Zwarts wrote:
>> Op 20.jun.2024 om 16:16 schreef 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 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>
>>>>
>>>> It seems you never learn. There is no correct simulation, 
>>>
>>> *You must have a reading comprehension problem*
>>> *H correctly simulates its input D*
>>> *until H correctly determines that its simulated D*
>>> *would never stop running unless aborted then*
>>
>> Each time again you tell things we already know. That does not help, 
>> because it is beside the point. Yes, It must abort, but when it aborts 
>> it is unable to see how the simulation would end.
> 
> Must abort means that it knows that simulation will
> not otherwise end. You can't even pay attention to
> the meaning of words.

But that is meaningless in your context.

You break your logic by making your argument change that which is being 
simulated as you step through it. That just shows you are lying.

Remember, A MACHINE/PROGRAM has behavior, but not a "template", as you 
can't just run the template, but only an instance of it,

And the "Correct Simulation" of this input, will halt, so H didn't have 
to abort it, but does.

If the mere fact that H aborting its simulation allows it to claim that 
it "must" then the condition of "must" is trivially derived.

> 
>>  Because the simulated H is only one cycle behind the simulating H, so 
>> one cycle later the simulated H would come to an end and halt as well, 
>> if the simulation were correct. This is the fate of a simulating 
>> decider: not aborting is wrong and aborting is always too early.
>>
>>>
>>> *This is simulating a finite number of steps of a non-terminating input*
>>
========== REMAINDER OF ARTICLE TRUNCATED ==========