Re: Every sufficiently competent C programmer knows

On 13/03/2025 15:44, Ben Bacarisse wrote:

I hope you forgive me just chipping in with stuff you know perfectly
well, but I thought I'd just give some background as Richard is a new
participant and my comments fit better with your post than his.

New to this debate, at any rate. :-)
It took me a while to get a handle on what OP was actually trying to achieve, because on face value it looked like he was claiming to have a decision algorithm, which he clearly hasn't. Mike Terry straightened me out there, and your news that the OP once wrote: "I really do have a halting decider" is certainly interesting.
I can't help thinking that, tempting though it might be to have a stab at cutting decider code, to do so is a mistake. I mean sure, if you manage to get one working you get to be the man who proved Turing wrong. But if you get one /almost/ working, to the point where it gives you the counter-theoretical answer you're expecting, there has to be a tendency to trust your own code a little too much, and it may be necessary to tweak reality a bit (those "stipulative definitions" of the OP's) to make it fit your code.
An example unrelated to HP:
Yesterday, I spent half an hour scouring the Web looking for bug reports of gcc failing to zero-fill partially initialised arrays. I was (foolish enough to be) convinced I'd uncovered a compiler bug.
The bug was, of course, in my own code --- and it was the kind of mistake I never, ever make in a handful of lines of astoundingly simple code, so I knew it wasn't my mistake... but it was.
I suspect that most programmers go through this from time to time. /Theory/ says `yes, okay, the compiler /might/ have bugs, but really truly it's probably your code that's wrong', but you can't quite bring yourself to believe the theory, especially when the code in front of you is, as mine was, self-evidently flawless.
Theory would have saved me time, if only I'd listened to it. Theory says that the OP's software cannot work as a solution to the Halting Problem because, no matter how clever it is, it is always possible to construct an input it can't handle correctly.
Having said that, I still maintain that thanks to thermodynamics the following decider is always correct:
int halts(program *p, data *d)
{
   return 1; /* EVERYTHING halts. */
}
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within