For future reference, since Peter Olcott keeps presenting his C program
HHH as a halt decider and repeatedly invokes supposed agreements from
other people in support of it, here are a few facts worth keeping together.
1. A concrete counterexample to HHH
Peter's published HHH contains a detector which, roughly speaking,
treats repetition of a CALL from the same address to the same function,
with no conditional branch in the relevant region, as evidence of
infinite recursion/non-halting.
I gave him this deliberately simple terminating program:
-a-a typedef void (*fn)(unsigned);
-a-a void F(unsigned);
-a-a void G(unsigned);
-a-a void Done(unsigned);
-a-a void Done(unsigned n)
-a-a {
-a-a-a-a-a-a (void)n;
-a-a }
-a-a void G(unsigned n)
-a-a {
-a-a-a-a-a-a fn next[2] = { F, Done };
-a-a-a-a-a-a fn p = next[n];
-a-a-a-a-a-a p(n + 1);
-a-a }
-a-a void F(unsigned n)
-a-a {
-a-a-a-a-a-a G(n);
-a-a }
-a-a void P(void)
-a-a {
-a-a-a-a-a-a F(0);
-a-a }
There is no global state hidden here.
The state is explicitly carried in the argument.
The execution is:
-a-a P
-a-a-a-a -> F(0)
-a-a-a-a -> G(0)
-a-a-a-a -> F(1)
-a-a-a-a -> G(1)
-a-a-a-a -> Done(2)
-a-a-a-a -> return
-a-a-a-a -> return
-a-a-a-a -> ...
-a-a-a-a -> halt
In particular, the same CALL instruction in F calls G more than once.
But the complete machine states are different: among other things, the argument is different.
So repetition of the same control location and target is NOT repetition
of the same computational configuration.
Peter actually ran his HHH on my example and reported:
-a-a My code did report 0 for non-halting on your input.
-a-a I don't know if this is correct or not.
-a-a HHH(P)==0 may have been correct, IDK.
It isn't correct.
P obviously halts, as the complete execution above shows.
When this was pointed out, Peter's answer was:
-a-a Then it is simply outside the domain of HHH.
That is worth remembering.
A program was presented.
HHH classified it as non-halting.
The program demonstrably halts.
The response was to exclude the counterexample from HHH's domain.
Unless a PRE-EXISTING definition of the domain independently excludes P, this is not a defence of an infallible halt decider. It is simply
defining counterexamples away after they have been found.
2. Why this also matters to DD
Peter's usual example is:
-a-a int DD()
-a-a {
-a-a-a-a-a-a int Halt_Status = HHH(DD);
-a-a-a-a-a-a if (Halt_Status)
-a-a-a-a-a-a-a-a-a-a for (;;);
-a-a-a-a-a-a return Halt_Status;
-a-a }
with the advertised semantics:
-a-a HHH(<P>) == 1 : P halts
-a-a HHH(<P>) == 0 : P does not halt
Hence:
-a-a +-----------+------------------+------------------+
-a-a | HHH(<DD>) | HHH predicts-a-a-a-a | DD then does-a-a-a-a |
-a-a +-----------+------------------+------------------+
-a-a |-a-a-a-a 1-a-a-a-a | DD halts-a-a-a-a-a-a-a-a | loops forever-a-a-a |
-a-a |-a-a-a-a 0-a-a-a-a | DD does not halt | returns / halts-a |
-a-a +-----------+------------------+------------------+
Peter's escape is to say that, while HHH simulates DD, DD calls HHH
again, producing nested simulation, and that DD therefore cannot reach
its return statement.
But the observation
-a-a HHH simulates DD
-a-a-a-a -> DD calls HHH
-a-a-a-a-a-a -> HHH simulates DD
-a-a-a-a-a-a-a-a -> DD calls HHH
-a-a-a-a-a-a-a-a-a-a-a ...
establishes a recursive PREFIX.
It does not establish that this recursion continues forever.
To establish that, Peter must prove that none of the relevant nested HHH calls can return.
Calling the desired conclusion a "simulation invariant", or saying that
the return statement is "unreachable", does not prove it.
The counterexample above is particularly relevant because it
demonstrates experimentally with Peter's own HHH that recognizing
repeated control-flow patterns while ignoring relevant computational
state can produce a false non-halting verdict.
3. The alleged Sipser endorsement
Peter also repeatedly quotes Michael Sipser:
-a-a If simulating halt decider H correctly simulates its
-a-a input D until H correctly determines that its simulated D
-a-a would never stop running unless aborted then
-a-a H can abort its simulation of D and correctly report that
-a-a D specifies a non-halting sequence of configurations.
Peter presents this prominently in discussions of his HHH.
But read what Sipser supposedly agreed to:
-a-a IF H CORRECTLY DETERMINES ...
Of course.
If a halt decider has correctly determined that a computation will never halt, then it may correctly report that it will not halt.
The disputed issue is precisely whether Peter's HHH has CORRECTLY
DETERMINED that.
Nothing in the quoted statement says that Peter's particular criterion establishes this premise.
Nothing there endorses his HHH implementation.
Nothing there proves that repeated nested simulation must continue forever.
The entire disputed step is already contained in the words:
-a-a correctly determines
So this quotation cannot honestly be presented as Sipser's endorsement
of Peter's proof. Sipser agreed to the conditional statement Peter
quotes, not to Peter's claim that HHH satisfies its premise.
4. The same thing happened with me
Peter has repeatedly tried to turn things I agreed with into agreement
with his conclusion.
For example, I agreed that applying the C operational semantics produces
the recursive simulation pattern:
-a-a HHH simulates DD
-a-a-a-a -> DD calls HHH(DD)
-a-a-a-a-a-a -> HHH simulates DD
-a-a-a-a-a-a-a-a -> ...
I did NOT agree that the "..." proves infinite recursion.
I did NOT agree that no nested HHH can return.
I did NOT agree that DD therefore cannot halt.
I did NOT agree that HHH(DD)==0 is therefore correct.
I explicitly told Peter this, repeatedly.
Eventually Peter himself wrote:
-a-a I did not realize that you did not mean:
-a-a IF HHH keeps simulating
-a-a that simulation does not naturally return.
-a-a I thought that you were saying the same exact
-a-a meaning more verbosely.
That is an explicit acknowledgement that he had misunderstood what I
agreed to.
After such an acknowledgement, there is no remaining ambiguity: my statements cannot legitimately be cited as agreement with the stronger proposition.--
The distinction is elementary but important:
-a-a agreeing with A
-a-a agreeing with A -> B
does not mean
-a-a agreeing with B
when the inference from A to B is precisely what is disputed.
The same applies to Sipser's conditional statement.
5. So, for future participants
When Peter says that somebody has "agreed" with his reasoning, ask for
the EXACT proposition that person agreed to.
When he quotes Sipser, notice the words:
-a-a correctly determines
and ask where Peter proves that his detector actually does so.
When he says repeated/nested simulation proves non-halting, remember the terminating P/F/G/Done counterexample above.
And when a counterexample is dismissed as "outside the domain" only
after HHH has produced the wrong answer on it, ask for the definition of that domain which existed BEFORE the counterexample was tested.
These points save a great deal of circular discussion.
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 76 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 56:59:00 |
| Calls: | 1,265 |
| Calls today: | 1 |
| Files: | 1,362 |
| D/L today: |
4 files (9,632K bytes) |
| Messages: | 285,828 |