Re: Every sufficiently competent C programmer knows --- posthumous reviewers

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.