Re: Every sufficiently competent C programmer knows

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 is true that sometimes his tests match and the input is indeed non-halting.  PO quotes this as evidence that his tests "work", so when the decided non-halting for a halting computation they must be correct and the halting computation in fact is non-halting because it "exhibited non-halting behaviour"!

 int rha(unsigned int i)
{
   while(--i > 0)while(--i > 0);
   return 0;
}
 int rhb(unsigned int i)
{
   if(i > 0)
   {
     rhb(i/10);
   }
   return putchar(i + '0');
}
 int rhc(unsigned int i)
{
   typedef int(*pf)(unsigned int);
   pf arr[3] = {rha, rhb, rhc};
   return arr[i % 3];
}
 and other such obvious tests.
 HHH(), the procedure that decides whether a program halts, is required to work for all programs and all inputs. Does it work on those cited above? I'm guessing it doesn't.
 

I would have to think a bit about your examples - or more likely just try them out (which I'm not motivated to do).  PO's non-halting tests involve observing loops and conditional branches in some combination.  The major problem for his HHH/DDD is with the simulation aspect - the tests can match when the same code address is reached but across completely different simulation levels.  PO does not appreciate that tests which /might/ work in a non-simulation setting, could go horribly wrong when simulation is involved...  (so your tests aren't especially relevant for PO's code logic - and as I said there is only the one case that he really has to handle.)
Mike.