Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows --- posthumous
 reviewers
Date: Thu, 13 Mar 2025 11:35:23 +0100
Organization: A noiseless patient Spider
Lines: 108
Message-ID: <vqucdc$36e14$1@dont-email.me>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqpv2u$23vhr$1@dont-email.me>
 <Ny-dnRlMHcVpA036nZ2dnZfqnPqdnZ2d@brightview.co.uk>
 <vqrjrn$2h4l2$1@dont-email.me>
 <nESdnUfJxdhoTkz6nZ2dnZfqnPSdnZ2d@brightview.co.uk>
 <vqsl7c$2ok91$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 13 Mar 2025 11:35:24 +0100 (CET)
Injection-Info: dont-email.me; posting-host="994dc4980cf59054a36339a8e5c96216";
	logging-data="3356708"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18WYDVXZEKbcHYNdnb4tSNU"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:2BWDoSRPzSa7GDl1IACxVMhzKM0=
In-Reply-To: <vqsl7c$2ok91$1@dont-email.me>
Content-Language: nl, en-GB
Bytes: 6787

Op 12.mrt.2025 om 19:53 schreef olcott:
> On 3/12/2025 1:35 PM, Mike Terry wrote:
>> On 12/03/2025 09:24, Fred. Zwarts wrote:
>>> Op 11.mrt.2025 om 21:37 schreef Mike Terry:
>>>> On 11/03/2025 18:23, Richard Heathfield wrote:
>>>>> On 11/03/2025 17:42, Mike Terry wrote:
>>>>>> Finally, if you really want to see the actual HHH code, its in the 
>>>>>> halt7.c file (along with DDD) that PO provides links to from time 
>>>>>> to time.  However it's not very illuminating due to bugs/design 
>>>>>> errors/ misunderstandings which only serve to obfuscate PO's 
>>>>>> errors in thinking.
>>>>>
>>>>> [I've now seen the code. Oh deary deary me.]
>>>>
>>>> :)
>>>>
>>>>>
>>>>> Thank you for a spirited attempt to be cogent - or at least as 
>>>>> cogent as it is possible to be in the circumstances!
>>>>>
>>>>> I think PO's first step must be to demonstrate that HHH() correctly 
>>>>> diagnoses some easy functions, such as these:
>>>>
>>>> Not really necessary - PO is not trying or claiming to have a (full) 
>>>> halt decider.
>>>>
>>>> Originally his claim was that he had a program which worked for the 
>>>> counter-example TM used in the common (e.g. Linz book) proof.  Such 
>>>> a program is impossible, as Linz and others prove, so having a 
>>>> program H and its corresponding "counter-example" D, such that H 
>>>> correctly decides D, would certainly show that the Linz proof is 
>>>> wrong.  His claim was always that he had "refuted the HP proof", or 
>>>> sometimes that he had refuted the HP theorem itself although he's 
>>>> been told dozens of times that there are many alternative proofs for 
>>>> the result.
>>>>
>>>> [As it turned out, PO's D(D) halted when run under his x86utm 
>>>> environment, while H(D,D) which is required to return the halting 
>>>> status of computation D(D) returned 0 (=non-halting).  That is 
>>>> exactly what the Linz proofs claim!]
>>>>
>>>> Anyhow, his decider only /has/ to correctly decide the one input, 
>>>> which is the D constructed from H by the usual method (basically D 
>>>> calls H to see what H claims is the halting behaviour, then does the 
>>>> opposite - I'm not sure if you're familiar with the proof, but 
>>>> imagine you would be given your background).
>>>>
>>>> His decider H works (subject to design errors/bugs and so on) by 
>>>> single- stepping a simulation of its input computation, and 
>>>> monitoring for conditions that PO believes indicate non-termination. 
>>>> He tests a couple of conditions, and when one of those matches H 
>>>> aborts and returns non- halting. Alternatively if the simulation 
>>>> halts normally, H returns halting.  The problem is (at least) one of 
>>>> his non-halting-behaviour tests is invalid, matching during the 
>>>> simulation of DDD, which is a halting computation.
>>>
>>> It seems that he does not understand that the these conditions (that 
>>> indicate non-termination behaviour), form exactly the halting problem.
>>> PO claims that simulation is the solution, but he only shifts the 
>>> problem of non-termination detection to the detection of these 
>>> 'special conditions'.
>>> When we realise that, we understand that a finite or infinite 
>>> simulation is not very relevant. The discussion should address these 
>>> conditions. But PO carefully avoids discussions about the detection 
>>> of these conditions, although they are the heart of the problem.
>>
>> I completely agree.
>>
>> We could create a (partial) simulating halt decider (PSHD) that works 
>> by simulating the steps of its input computation, and looking for 
>> patterns in the resulting trace indicating halting or non-halting 
>> behaviour.  If these patterns were /*sound*/, meaning that matching 
>> guarantees the computation behaviour is indeed halting/non-halting as 
>> the test claims, then the PSHD could abort the simulation and decide 
>> halting behaviour correctly on that basis.  [This much is obvious, and 
>> is basically what Sipser means in his "agreement" statement that PO 
>> often quotes, although PO has his own differing interpretation of what 
>> that means.]
>>
> 
> _DDD()
> [00002172] 55         push ebp      ; housekeeping
> [00002173] 8bec       mov  ebp,esp  ; housekeeping
> [00002175] 6872210000 push 00002172 ; push DDD
> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
> [0000217f] 83c404     add  esp,+04
> [00002182] 5d         pop  ebp
> [00002183] c3         ret
> Size in bytes:(0018) [00002183]
> 
> When DDD is emulated by HHH according to the semantics
> of the above x86 machine language then DDD cannot possibly
> reach past its own machine address 0000217a.

That HHH fails to reach the relevant part of the simulation is 
completely irrelevant and does not address what was said.
> 
> My posthumous reviewers will notice that my current
> reviewers were disingenuous to the extent of dishonesty
> on this specific point.

I don't think so, because they will see that we agree that HHH fails to 
reach the end of the simulation, because it aborts on unsound ground.

They will also see that Olcott agrees that the simulation is incomplete 
for this input, for which direct execution and world-class simulators 
have no problem to reach the end of exactly the same input.