Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: How Partial Simulations correctly determine non-halting ---Mike
 Terry Error
Date: Wed, 5 Jun 2024 10:21:21 +0200
Organization: A noiseless patient Spider
Lines: 90
Message-ID: <v3p761$sg73$4@dont-email.me>
References: <v3j20v$3gm10$2@dont-email.me>
 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <87h6eamkgf.fsf@bsb.me.uk> <v3kcdj$3stk9$1@dont-email.me>
 <v3l7uo$13cp$8@dont-email.me> <v3lcat$228t$3@dont-email.me>
 <v3mq9j$chc3$1@dont-email.me> <v3mrli$chc4$1@dont-email.me>
 <_gWdnbwuZPJP2sL7nZ2dnZfqn_GdnZ2d@brightview.co.uk>
 <v3nkqr$h7f9$3@dont-email.me> <v3o0ph$31rmn$1@i2pn2.org>
 <v3o3og$jm9q$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 05 Jun 2024 10:21:22 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e6d5df0eda1d70253dfad5dc15939df5";
	logging-data="934115"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Yv2tQYn9TOZ4FWLEf2eb8"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:9bl664l7W4nJYCZHFhFlU1u0/dE=
Content-Language: en-GB
In-Reply-To: <v3o3og$jm9q$2@dont-email.me>
Bytes: 5114

Op 05.jun.2024 om 00:16 schreef olcott:
> On 6/4/2024 4:26 PM, joes wrote:
>> Am Tue, 04 Jun 2024 13:02:03 -0500 schrieb olcott:
>>> On 6/4/2024 11:58 AM, Mike Terry wrote:
>>>> On 04/06/2024 11:52, Fred. Zwarts wrote:
>>>>> Op 04.jun.2024 om 12:29 schreef Fred. Zwarts:
>>>>>> Op 03.jun.2024 om 23:24 schreef olcott:
>>>>>>> On 6/3/2024 3:09 PM, Fred. Zwarts wrote:
>>>>>>>> Op 03.jun.2024 om 14:20 schreef olcott:
>>>>>>>>> On 6/3/2024 4:42 AM, Ben Bacarisse wrote:
>>>>>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>>>>>
>>>>>>>>> *DD correctly simulated by HH would never stop running unless
>>>>>>>>> aborted*
>>>>>>>>> *We can see that the following DD cannot possibly halt when*
>>>>>>>>> *correctly simulated by every HH that can possibly exist*
>>>>>>>>
>>>>>>>> It is very clear that if the simulated HH would halt, then DD would
>>>>>>>> halt. So your claim comes down to HH not halting when simulating
>>>>>>>> itself.
>>>>>>>>
>>>>>>> Mike Terry replied to this and explained it correctly as reply
>>>>>>> directly to you On 6/3/2024 12:36 PM, Mike Terry wrote:
>>>>>>>
>>>>>>> http://al.howardknight.net/?
>> STYPE=msgid&MSGI=%3CHlGdnbvc3Ly_YsD7nZ2dnZfqn_adnZ2d%40brightview.co.uk%3E
>>>>>>>
>>>>>>>
>>>>>> He says that there is no infinite recursion, because the simulation
>>>>>> is aborted.
>>>>>> If you want to interpret his reply in this way,
>>>>
>>>> Yes, that's my intended meaning
>>>>
>>>>> then it also shows that neither HH, nor DD are
>>>>>> involved in a recursive recursion. This implies
>>>>>
>>>>> That should be: ... are involved in an infinite recursion, because the
>>>>> simulation was aborted,
>>>>
>>>> Yes.  (There is finite recursive simulation, i.e. H partially simulates
>>>> H etc..)
>>>>
>>>>> which implies ...
>>>>>
>>>>>> that none of them reaches their final state.
>>>>
>>>> None of their /simulations by H/ reach their final state.  Obviously
>>>> there's a huge distinction between the abstract concept of a
>>>> computation/halting, and a partial simulation of that computation by
>>>> some other program, and I'm surprised anyone (not you specifically)
>>>> tolerates confusion on that point.
>>>>
>>>> Suppose P(I) is some computation that halts after 13422 steps.  Clearly
>>>> a partial simulation of P(I) by H could be abandoned ("aborted") after
>>>> 8333 steps.  So the /partial simulation by H/ "does not halt", but the
>>>> computation P(I) of course halts.
>>>>
>>>> I'm not trying to suggest that considering the "halting" behaviour of a
>>>> partial simulation by a specific program is a /useful/ thing to be
>>>> looking at, but none the less that is what PO is doing...
>>>>
>>> The meaning of these words prove that I am correct about how partial
>>> simulations correctly determine the halt status of their non-halting
>>> inputs.
>>> <Professor Sipser agreed>
>>> </Professor Sipser agreed>
>>
>> You completely missed the point. The simulator absolutely can keep track
>> of repeating states; it just can't halt if its input doesn't, 
> 
> You don't seem to know the first thing about deciders, in that
> they must always halt.
> 

Yes. And the fact that your decider diagnoses itself as non-halting 
proves that there is something wrong with your decider.
Get the cream out of your eyes!

        typedef int (*ptr)();  // ptr is pointer to int function in C

        int H(ptr p, ptr i);

        int main()
        {
          H(main, 0);
        }

H diagnoses this program as non-halting. The only reason is obvious: the 
simulation of H by itself did not reach the final state.