Path: ...!news.tomockey.net!2.eu.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Can D simulated by H terminate normally?
Date: Sun, 5 May 2024 11:14:17 +0300
Organization: -
Lines: 127
Message-ID: <v17f4p$1ojbj$1@dont-email.me>
References: <v0k4jc$laej$1@dont-email.me> <v0l11u$ussl$1@dont-email.me> <v0lh24$123q3$1@dont-email.me> <v0lic7$2g492$3@i2pn2.org> <v0lkas$12q0o$3@dont-email.me> <v0loq2$2g493$1@i2pn2.org> <v0lq7d$14579$2@dont-email.me> <v0ls98$2g492$7@i2pn2.org> <v0m29q$166o1$1@dont-email.me> <v0m37e$2gl1e$1@i2pn2.org> <v0m3v5$16k3h$1@dont-email.me> <v0m55t$2gl1f$3@i2pn2.org> <v0m5sn$172p4$1@dont-email.me> <v0oban$1o3b$1@news.muc.de> <v0oce3$1q3aq$4@dont-email.me> <v0oe1b$1o3b$2@news.muc.de> <v0ofl3$1r1mf$1@dont-email.me> <v0oh7g$1o3b$3@news.muc.de> <v0olhv$1sgeo$1@dont-email.me> <v0oobd$1o3b$4@news.muc.de> <v0or07$1tmga$1@dont-email.me> <v0qb59$2bsfc$1@dont-email.me> <v0r242$2hb7o$1@dont-email.me> <v0r3kh$hka$1@news.muc.de> <v0r5f2$2hb7o$11@dont-email.me> <v0rsbv$2m1nf$8@i2pn2.org> <v0sgcm$2varu$3@dont-email.me> <v0vmvu$209h$3@news.muc.de> <v10md7$ese$1@dont-email.me> <v12b14$fbko$1@dont-email.me> <v12jb4$hc81$1@dont-email.me> <v1507m$1549l$1@dont-email.me> <v15eqb$17unh$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 05 May 2024 10:14:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b9d6f5138f29339683dcbf59468f91f0";
	logging-data="1854835"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/5sr/erN1D4APAHbV7HVxa"
User-Agent: Unison/2.2
Cancel-Lock: sha1:k/C3ync+tcb4BoQpfULuJQcYXHg=
Bytes: 6236

On 2024-05-04 13:56:27 +0000, olcott said:

> On 5/4/2024 4:47 AM, Mikko wrote:
>> On 2024-05-03 11:55:15 +0000, olcott said:
>> 
>>> On 5/3/2024 4:33 AM, Mikko wrote:
>>>> On 2024-05-02 18:35:19 +0000, olcott said:
>>>> 
>>>>> On 5/2/2024 4:39 AM, Alan Mackenzie wrote:
>>>>>> olcott <polcott333@gmail.com> wrote:
>>>>>>> On 4/30/2024 5:46 PM, Richard Damon wrote:
>>>>>>>> On 4/30/24 12:15 PM, olcott wrote:
>>>>>>>>> On 4/30/2024 10:44 AM, Alan Mackenzie wrote:
>>>>>>>>>> olcott <polcott333@gmail.com> wrote:
>>>>>>>>>>> On 4/30/2024 3:46 AM, Fred. Zwarts wrote:
>>>>>>>>>>>> Op 29.apr.2024 om 21:04 schreef olcott:
>>>>>> 
>>>>>> [ .... ]
>>>>>> 
>>>>>>>>> When we add the brand new idea of {simulating termination analyzer} to
>>>>>>>>> the existing idea of TM's then we must be careful how we define halting
>>>>>>>>> otherwise every infinite loop will be construed as halting.
>>>>>> 
>>>>>> 
>>>>>>>> Why?
>>>>>> 
>>>>>>>> That doesn't mean the machine reached a final state.
>>>>>> 
>>>>>> 
>>>>>>> Alan seems to believe that a final state is whatever state that an
>>>>>>> aborted simulation ends up in.
>>>>>> 
>>>>>> Only through your twisted reasoning.  For your information, I hold to the
>>>>>> standard definition of final state, i.e. one which has no state following
>>>>>> it.  An aborted simulation is in some state, and that state is a final
>>>>>> one, since there is none following it.
>>>>>> 
>>>>>>> On 4/30/2024 10:44 AM, Alan Mackenzie wrote:
>>>>>>>> You are thus mistaken in believing "abnormal" termination
>>>>>>>> isn't a final state.
>>>>>> 
>>>>>>>> Only if you try to define something that is NOT related to Halting, do
>>>>>>>> you get into that issue.
>>>>>> 
>>>>>>> "The all new ideas are wrong" assessment.
>>>>>>> Simulating termination analyzers <are> related to halting.
>>>>>> 
>>>>>> Except you cannot define what such a thing is, and that relationship is
>>>>>> anything but clear.
>>>>> 
>>>>> When a simulating termination analyzer matches one of three
>>>>> non-halting behavior patterns
>>>>> (a) Simple Infinite loop
>>>>> (b) Simple Infinite Recursion
>>>>> (c) Simple Recursive Simulation
>>>> 
>>>> Simple recursive simulation is not a non-halting behaviour
>>>> if the recursion is not infinite.
>>> 
>>> In other words the only way that we can tell that an infinite
>>> loop never halts is to simulate it until the end of time?
>> 
>> The phrase "in other words" is not correct here as it means that
>> what follows means the same as what precedes, and that is not
>> true here.
>> 
>> For same loops the only wha to detect non-termination may be
>> to simulate to infinity but they can be considered exluded by
>> the term "simple" in (a).
>> 
>>> There are repeating state non-halting behavior patterns
>>> that can be recognized. These are three more functions
>>> where H derives the correct halt status:
>>> 
>>> void Infinite_Recursion(u32 N)
>>> {
>>>    Infinite_Recursion(N);
>>> }
>> 
>> Per (b) that is non-halting and indeed it is (though the
>> execution may crash for "out of memeory").
>> 
> 
> It is not actually infinite though because H recognizes the non-halting
> behavior pattern, aborts the simulation and reports non-halting.

The recursion is infinite. The simulation by H is incomplete and finite.

> It is the exact same thing with D simulated by H on the basis
> of the directly executed H(D,D).
> 
>>> void Infinite_Loop()
>>> {
>>>    HERE: goto HERE;
>>> }
>> 
>> Per (a) that is non-halting and indeed it is.
> 
> It is not actually infinite though because H recognizes the non-halting
> behavior pattern, aborts the simulation and reports non-halting.

The loop is infinite. The simulation by H is incomplete and finite.

> It is the exact same thing with D simulated by H on the basis
> of the directly executed H(D,D).
> 
>> 
>>> int factorial(int n)
>>> {
>>>    if (n >= 1)
>>>      return n*factorial(n-1);
>>>    else
>>>      return 1;
>>> }
>> 
>> Per (c) that is non-halting but in reality it is not.
>> Ergo, the rule (c) is wrong.
> 
> That was an example of an input that H correctly determines
> does halt.

Maybe but it is an example of your non-halting pattern (c) as
presented above.

-- 
Mikko