Subject: Re: Olcott's HHH: the counterexample, the missing proof, and borrowed "agreements"
On 10/31/2026 12:29 PM, Python wrote:
WHY THIS REFERENCE POST IS NEEDED
This post is intended as a reference for present and future participants
in these discussions.
It has become increasingly difficult to follow Peter Olcott's claims
about his C implementation of HHH because the same argument is spread
over many threads and repeatedly restarted from different points.
Three facts in particular tend to disappear when this happens:
1. A concrete terminating counterexample was actually submitted to
Peter's HHH, which classified it as non-halting. Once its termination
was pointed out, Peter's response was that the program was outside HHH's domain.
2. Peter repeatedly cites limited agreements by other people -- notably Michael Sipser and myself -- as support for substantially stronger
claims which those people did not agree to.
3. When people examine the crucial call to HHH occurring inside
simulated DD, Peter now sometimes declares that they are "changing the subject away from the behavior of DD simulated by HHH", even though that call is literally part of the execution of DD being simulated.
Rather than reconstructing this history every time a new participant
enters the discussion, here are the relevant facts in one place.
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:
˙˙ typedef void (*fn)(unsigned);
˙˙ void F(unsigned);
˙˙ void G(unsigned);
˙˙ void Done(unsigned);
˙˙ void Done(unsigned n)
˙˙ {
˙˙˙˙˙˙ (void)n;
˙˙ }
˙˙ void G(unsigned n)
˙˙ {
˙˙˙˙˙˙ fn next[2] = { F, Done };
˙˙˙˙˙˙ fn p = next[n];
˙˙˙˙˙˙ p(n + 1);
˙˙ }
˙˙ void F(unsigned n)
˙˙ {
˙˙˙˙˙˙ G(n);
˙˙ }
˙˙ void P(void)
˙˙ {
˙˙˙˙˙˙ F(0);
˙˙ }
There is no global state hidden here.
The relevant state is explicitly carried in the argument.
Its execution is:
˙˙ P
˙˙˙˙ -> F(0)
˙˙˙˙ -> G(0)
˙˙˙˙ -> F(1)
˙˙˙˙ -> G(1)
˙˙˙˙ -> Done(2)
˙˙˙˙ -> return
˙˙˙˙ -> return
˙˙˙˙ -> ...
˙˙˙˙ -> halt
In particular, the same CALL instruction in F calls G more than once.
But the complete computational states are different: among other things,
the argument is different.
Therefore repetition of the same CALL instruction and target is NOT repetition of the same computational configuration.
Peter actually ran his HHH on this example and reported:
˙˙ My code did report 0 for non-halting on your input.
˙˙ I don't know if this is correct or not.
˙˙ HHH(P)==0 may have been correct, IDK.
It isn't correct.
P plainly halts, as the execution above shows.
When this was pointed out, Peter's response was:
˙˙ Then it is simply outside the domain of HHH.
This is worth remembering.
A program was presented.
HHH classified it as non-halting.
The program demonstrably halts.
The response was then to exclude that program from HHH's domain.
Unless a PRE-EXISTING definition of HHH's domain independently excludes
P, this does not rescue a claim that HHH is infallible over some
previously specified domain.
It merely excludes a counterexample after HHH has produced the wrong
answer on it.
Anyone wishing to defend the "outside the domain" response should
therefore provide the definition of HHH's domain that existed BEFORE
this test and show how that definition excludes P independently of the
fact that HHH got P wrong.
2. WHY THIS ALSO MATTERS TO DD
Peter's usual example is:
˙˙ typedef int (*ptr)();
˙˙ int HHH(ptr P);
˙˙ int DD()
˙˙ {
˙˙˙˙˙˙ int Halt_Status = HHH(DD);
˙˙˙˙˙˙ if (Halt_Status)
˙˙˙˙˙˙˙˙˙˙ HERE: goto HERE;
˙˙˙˙˙˙ return Halt_Status;
˙˙ }
with the advertised output semantics:
˙˙ HHH(<P>) == 1 : HHH says P halts
˙˙ HHH(<P>) == 0 : HHH says P does not halt
The consequence is immediate:
˙˙ +-----------+------------------+------------------+-------------+
˙˙ | HHH(<DD>) | HHH says˙˙˙˙˙˙˙˙ | DD then does˙˙˙˙ | HHH correct?|
˙˙ +-----------+------------------+------------------+-------------+
˙˙ |˙˙˙˙ 1˙˙˙˙ | DD halts˙˙˙˙˙˙˙˙˙ | loops forever˙˙˙ |˙˙˙˙ NO˙˙˙˙˙ |
˙˙ |˙˙˙˙ 0˙˙˙˙ | DD does not halt˙ | returns / halts˙ |˙˙˙˙ NO˙˙˙˙˙ |
˙˙ +-----------+------------------+------------------+-------------+
There is of course a third possibility:
˙˙ HHH(<DD>) does not return.
But then HHH is not a terminating halt decider for this input.
Peter's proposed escape is that, while HHH simulates DD, DD calls HHH
again, producing nested simulation, and therefore simulated DD cannot
reach its return statement.
The observation
˙˙ HHH simulates DD
˙˙˙˙ -> DD calls HHH(DD)
˙˙˙˙˙˙ -> HHH simulates DD
˙˙˙˙˙˙˙˙ -> DD calls HHH(DD)
˙˙˙˙˙˙˙˙˙˙˙ -> ...
certainly establishes the beginning of a recursive simulation pattern.
That point is not disputed.
The above recursive simulation continues while DD is simulated by HHH
<snip> of everything not directly related to
this one single point.
We cannot move on to any other points until
this one single point is fully resolved.
--
Copyright 2026 Olcott
Computation(Olcott)
Paraphrase of Emil Post definition of computation
All computations are equivalent to the application of finite
string transformation rules to finite string inputs to derive
any and all outputs.
Because Post canonical systems are Turing-equivalent, anything
that cannot be derived by applying finite string transformations
to finite strings is outside the scope of Church?Turing computation.
Decider(Olcott)
Correcting the misnomer term-of-the-art: decider
Every Decider(Olcott) must apply finite string transformation
inference steps to their finite string inputs that are relevant
to the decision criteria. It must make its decision on this basis.
Halt Decider(Olcott)
Decider(Olcott) entails that Halt Decider(Olcott) H(D) must apply
finite-string inference steps according to the operational semantics
of the source-code computation language of D. The only way to determine
the halting property of a finite string input is to examine the same
beha