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: How Partial Simulations correctly determine non-halting ---Mike
 Terry Error
Date: Wed, 5 Jun 2024 08:29:28 -0500
Organization: A noiseless patient Spider
Lines: 212
Message-ID: <v3pp7p$v133$8@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> <v3p4ka$sk6h$1@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 15:29:29 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="dbcb5a2e000d59c1dda264f94a647a93";
	logging-data="1016931"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18lop6K4ibgZDIXJ5heHZzo"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:+X58AcA/kueEBRlfNi7x75Lf36g=
In-Reply-To: <v3p4ka$sk6h$1@dont-email.me>
Content-Language: en-US
Bytes: 10119

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)
>> {
>>      H(Infinite_Recursion2, (ptr)N);
>> }
>>
>> That you continue to insist that either I misinterpreted my own
>> words or professor Sipser interpreted them differently than their
>> meaning that would correctly determine the halt status of the
>> above example at this point seem quite disingenuous especially
========== REMAINDER OF ARTICLE TRUNCATED ==========