Path: ...!news.misty.com!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: How Partial Simulations correctly determine non-halting ---Mike Terry Error
Date: Wed, 5 Jun 2024 10:37:46 +0300
Organization: -
Lines: 177
Message-ID: <v3p4ka$sk6h$1@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 05 Jun 2024 09:37:46 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f59ac17d296a13bc5d3841a994cc1bf4";
	logging-data="938193"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/52zedw1Ivr/ns0YH2SRH5"
User-Agent: Unison/2.2
Cancel-Lock: sha1:RZZkNBcrgGCqmA7j4PhKVdEsNQI=
Bytes: 9023

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
> when you provide zero reasoning to support this "misinterpretation"
> assertion.
> 
> *HOW PARTIAL SIMULATIONS CORRECTLY DETERMINE NON-HALTING*
> 
> 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>

It is quite clear what Professor Sipser agreed. If you use those words
as the second last part of your proof then it sould be obvious that we
need to look at the other parts in order to find an error in the proof.

-- 
Mikko