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: How Partial Simulations correctly determine non-halting ---Mike
 Terry Error
Date: Wed, 5 Jun 2024 19:54:05 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v3qtqt$354ia$4@i2pn2.org>
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> <v3p4ka$sk6h$1@dont-email.me>
 <v3pp7p$v133$8@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 5 Jun 2024 23:54:05 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3314250"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <v3pp7p$v133$8@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 10332
Lines: 220

On 6/5/24 9:29 AM, olcott wrote:
> On 6/5/2024 2:37 AM, Mikko wrote:
>> On 2024-06-04 18:02:03 +0000, olcott said:
>>
>>> 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:
>>>>>>>>>>
>>>>>>>>>>> PO's D(D) halts, as illustrated in various traces that have 
>>>>>>>>>>> been posted here.
>>>>>>>>>>> PO's H(D,D) returns 0 : [NOT halting] also as illustrated in 
>>>>>>>>>>> various traces.
>>>>>>>>>>> i.e. exactly as the Linz proof claims.  PO has acknowledged 
>>>>>>>>>>> both these
>>>>>>>>>>> results.  Same for the HH/DD variants.
>>>>>>>>>>>
>>>>>>>>>>> You might imagine that's the end of the matter - PO failed.  :)
>>>>>>>>>>>
>>>>>>>>>>> That's right, but PO just carries on anyway!
>>>>>>>>>>
>>>>>>>>>> He has quite explicitly stated that false (0) is the correct 
>>>>>>>>>> result for
>>>>>>>>>> H(D,D) "even though D(D) halts".  I am mystified why anyone 
>>>>>>>>>> continues to
>>>>>>>>>> discuss the matter until he equally explicitly repudiates that 
>>>>>>>>>> claim.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Deciders only compute the mapping *from their inputs* to their own
>>>>>>>>> accept or reject state. The correct emulation of the machine 
>>>>>>>>> code input
>>>>>>>>> to H(DD,DD) requires DD emulated by HH to emulate each x86 
>>>>>>>>> instruction
>>>>>>>>> of the x86 machine code of DD correctly and in the correct order.
>>>>>>>>>
>>>>>>>>> *The input to HH(DD,DD) specifies non-halting behavior*
>>>>>>>>>
>>>>>>>>> The only way to cause DD emulated by HH to have the same 
>>>>>>>>> behavior as
>>>>>>>>> the directly executed (non input) DD(DD) is to emulate the 
>>>>>>>>> instructions
>>>>>>>>> specified by the machine code of DD incorrectly or in the 
>>>>>>>>> incorrect
>>>>>>>>> order. *This is not the behavior that the input to HH(DD,DD) 
>>>>>>>>> specifies*
>>>>>>>>>
>>>>>>>>> The behavior of the directly executed DD(DD) has different 
>>>>>>>>> behavior
>>>>>>>>> than DD correctly emulated by HH. This is because the behavior 
>>>>>>>>> of DD(DD)
>>>>>>>>> reaps the benefits of HH having already aborted its simulation.
>>>>>>>>>
>>>>>>>>> No one ever noticed that these two behaviors could ever diverge 
>>>>>>>>> before
>>>>>>>>> because everyone rejected the notion of a simulating halt 
>>>>>>>>> decider out-
>>>>>>>>> of-hand without review.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Two PhD computer science professors that I have communicated with
>>>>>>>>> agree with me that there is something wrong with the halting 
>>>>>>>>> problem.
>>>>>>>>>
>>>>>>>>> Bill Stoddart. *The Halting Paradox*
>>>>>>>>> 20 December 2017
>>>>>>>>> https://arxiv.org/abs/1906.05340
>>>>>>>>> arXiv:1906.05340 [cs.LO]
>>>>>>>>>
>>>>>>>>> E C R Hehner. *Problems with the Halting Problem*, 
>>>>>>>>> COMPUTING2011 Symposium on 75 years of Turing Machine and 
>>>>>>>>> Lambda-Calculus, Karlsruhe Germany, invited, 2011 October 
>>>>>>>>> 20-21; Advances in Computer Science and Engineering v.10 n.1 
>>>>>>>>> p.31-60, 2013
>>>>>>>>> https://www.cs.toronto.edu/~hehner/PHP.pdf
>>>>>>>>>
>>>>>>>>> E C R Hehner. *Objective and Subjective Specifications*
>>>>>>>>> WST Workshop on Termination, Oxford.  2018 July 18.
>>>>>>>>> See https://www.cs.toronto.edu/~hehner/OSS.pdf
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> *Introduction to the Theory of Computation, by Michael Sipser*
>>>>>>>>> https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/
>>>>>>>>>
>>>>>>>>> On 10/13/2022 11:29:23 AM
>>>>>>>>> MIT Professor Michael Sipser agreed this verbatim paragraph is 
>>>>>>>>> correct
>>>>>>>>> (He has neither reviewed nor agreed to anything else in this 
>>>>>>>>> paper)
>>>>>>>>>
>>>>>>>>> <Professor Sipser agreed>
>>>>>>>>> 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.
>>>>>>>>> </Professor Sipser agreed>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> *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.
>>>
>>> Those words are dead obviously correct about how a partial simulation
>>> does correctly determine the halt status of this function:
>>>
>>> void Infinite_Recursion2(u32 N)
>>> {
========== REMAINDER OF ARTICLE TRUNCATED ==========