Path: ...!weretis.net!feeder8.news.weretis.net!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: Thu, 20 Jun 2024 11:35:13 -0500
Organization: A noiseless patient Spider
Lines: 100
Message-ID: <v51lo1$2kst7$2@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>
 <v4uvu0$21os1$4@dont-email.me> <v50ot4$2fh9b$1@dont-email.me>
 <v51dk0$2jmrd$2@dont-email.me> <v51ldd$inq6$2@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 20 Jun 2024 18:35:14 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f3edc3033c9d2f90d2fdc1ea5e7f24e7";
	logging-data="2782119"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/0TXoTK0e46llrv9vMM0es"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ldODCE7nBIxZDfDbEq+8LZ5WD1E=
Content-Language: en-US
In-Reply-To: <v51ldd$inq6$2@i2pn2.org>
Bytes: 5799

On 6/20/2024 11:29 AM, joes wrote:
> 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.
> 

*Yet sufficient to conclude*

<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 words 10/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