Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: joes <noreply@example.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Simulating termination analyzers by dummies --- What does halting
 mean?
Date: Thu, 20 Jun 2024 16:29:33 -0000 (UTC)
Organization: i2pn2 (i2pn.org)
Message-ID: <v51ldd$inq6$2@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 20 Jun 2024 16:29:33 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="614214"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="x7oam9g+YJaeV9OTOtIJoUo/SZzgHQcpSdTmknMf03k";
User-Agent: Pan/0.145 (Duplicitous mercenary valetism; d7e168a
 git.gnome.org/pan2)
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 5002
Lines: 85

Am Thu, 20 Jun 2024 09:16:32 -0500 schrieb 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 halts iff H0 halts.

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

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

>>>>>> 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 DDD()
>>>>> {
>>>>>    H0(DDD);
>>>>> }
>>>>> int main()
>>>>> {
>>>>>    H0(DDD);
>>>>> }
>>>>>
>>>>> Every C programmer that knows what an x86 emulator is knows that
>>>>> when H0 emulates the machine language of
>>>>> 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*
>>> [blah blah Sipser]
>> 
>> It seems you never learn. There is no correct simulation,
>> so Sipser words do not apply.
> Either not paying attention or deliberately deceptive.

> *H correctly simulates its input D*
> *until H correctly determines that its simulated D*
whence it stops simulating (correctly, or at all)
> *would never stop running unless aborted then*
stops simulating the following steps.
> *This is simulating a finite number of steps of a non-terminating input*
I.e. not a full simulation.

-- 
Man kann mit dunklen Zahlen nicht rechnen. Für die eigentliche Mathematik 
sind sie vollkommen nutzlos. --Wolfgang Mückenheim