Subject: Olcott's HHH: the counterexample, the missing proof, and borrowed "agreements"

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

H0 simulates D0
-> D0 calls H1
-> H1 simulates D1
-> D1 calls H2
-> ...

certainly establishes the beginning of a recursive simulation pattern.

That point is not disputed.

What IS disputed is the additional inference:

therefore this nesting necessarily continues forever
and no relevant nested HHH call can return.

This distinction is crucial because Peter now sometimes answers the
objection with formulations such as:

The above recursive simulation continues
while DD is simulated by HHH.

That statement does NOT establish the required conclusion.

There are two very different propositions here:

A. WHILE the recursive simulation continues,
DD has not yet returned.

and:

B. The recursive simulation continues FOREVER,
therefore DD never returns.

A is trivial.

B is what Peter needs to prove.

A does not imply B.

Similarly:

WHILE HHH keeps recursively simulating DD,
the current simulated DD has not returned

does not imply:

HHH keeps recursively simulating DD FOREVER.

The word "while" describes what is true DURING some interval or process.

It does not establish that the interval or process has infinite duration.

For example:

while F is recursively calling itself,
F has not yet returned

can be perfectly true of a recursion that later bottoms out and returns.

Thus this:

H0 simulates D0
-> D0 calls H1
-> H1 simulates D1
-> D1 calls H2

establishes two nested calls.

For any finite n, continuing the same reasoning can establish n nested
calls, PROVIDED none of the earlier calls has returned before then.

But:

for every finite n we can describe another
nesting step conditional on reaching it

is not itself a proof that:

no Hn ever returns.

That is precisely the proposition which remains to be established.

In particular, consider some nested level Hn evaluating Dn.

Dn reaches:

Halt_Status = Hn+1(DD);

If Hn+1 returns 0, then the C execution is:

Halt_Status = 0
-> condition false
-> skip the loop
-> return 0

and Dn reaches its final state.

So Peter cannot establish that Dn cannot reach its final state merely by saying that Hn+1 starts another simulation.

He must establish that Hn+1 NEVER RETURNS 0.

And if the proof that Hn+1 never returns is simply:

Hn+1 simulates Dn+1,
which calls Hn+2

then exactly the same question has merely been moved one level deeper:

Why can't Hn+2 return 0?

Repeating the question at every finite depth does not answer it.

This is the precise gap between:

recursive nesting

and:

infinite recursion.

It is also why the phrase:

while DD is simulated by HHH

cannot close the argument.

If "while DD is simulated" is intended merely to describe the period
during which simulation is taking place, the statement is trivial and does
not prove that period infinite.

If instead Peter intends:

DD remains simulated by HHH forever

then he has simply inserted the disputed conclusion into the premise.

Either interpretation fails to provide the missing proof.

Calling the desired conclusion a:

"simulation invariant"

does not change this.

An invariant must be established, not merely named.

And saying that DD's return statement is:

"unreachable"

does not establish it either.

Indeed, if the HHH called by DD returns 0, the C semantics are straightforward:

Halt_Status = 0;
if (Halt_Status) // false
goto HERE; // not executed
return Halt_Status; // DD halts

So claiming that the return statement is unreachable already requires establishing that HHH cannot return 0 to DD.

That is precisely the disputed proposition.

The terminating P/F/G/Done counterexample is relevant here because it demonstrates concretely that recognizing repeated control-flow structure
while ignoring relevant computational state is not sufficient to establish non-halting.


3. EXAMINING THE SIMULATED HHH CALL IS NOT "CHANGING THE SUBJECT"

Peter has responded to objections with statements such as:

Changing the subject away from the behavior of DD
simulated by HHH while DD is being simulated by HHH

ONE-MORE-TIME ENDS THIS CONVERSATION

But examining what happens to the HHH(DD) invocation at line 03 is not changing the subject away from the behavior of simulated DD.

IT IS THE BEHAVIOR OF SIMULATED DD.

Look at the program:

01 int DD()
02 {
03 int Halt_Status = HHH(DD);
04 if (Halt_Status)
05 HERE: goto HERE;
06 return Halt_Status;
07 }

To simulate DD according to the operational semantics of C, the simulator eventually reaches line 03.

At that point DD invokes HHH(DD).

The subsequent behavior of DD depends on what happens to that invocation.

There are only the relevant possibilities:

HHH(DD) returns 1
-> Halt_Status becomes 1
-> line 04 is true
-> DD loops at line 05

HHH(DD) returns 0
-> Halt_Status becomes 0
-> line 04 is false
-> line 05 is skipped
-> DD reaches line 06 and returns

HHH(DD) does not return
-> DD remains waiting at line 03

Therefore the question:

Can the simulated HHH(DD) invocation return 0?

is not a change of subject.

It is the CENTRAL question determining the behavior of simulated DD.

Peter has repeatedly demanded:

show exactly how DD reaches its return statement
on line 06 while DD is being simulated by HHH

Mikko gave the exact answer:

simulated HHH(DD) returns 0
|
v
Halt_Status = 0
|
v
line 04 condition is false
|
v
line 05 is skipped
|
v
line 06: return 0

That is literally an execution path of simulated DD under the C
operational semantics.

Peter then called this a:

DISHONEST DODGE AWAY FROM THE POINT

But it is exactly the point he asked to be addressed.

If Peter wants to rule this execution path out, he must prove:

simulated HHH(DD) cannot return 0.

He cannot prove that proposition merely by repeating:

simulated DD invokes simulated HHH(DD)
which simulates DD

because that establishes another level of nesting, not that the nesting is infinite.

Nor can he prove it by saying:

DD cannot reach line 06

because that is merely the consequence he is trying to establish.

Nor does this formulation help:

The recursive simulation continues
while DD is simulated by HHH.

Again:

"continues while X"

is not:

"continues forever."

If the inner HHH returns 0, the recursive simulation stops being recursive
at that level and DD continues to line 06.

Therefore whether that inner HHH can return is not a diversion from the behavior of simulated DD.

It is exactly what determines that behavior.

Declaring discussion of the return behavior of HHH at line 03 to be
"changing the subject" makes the requested proof impossible by definition:
it excludes discussion of the very operation whose behavior determines
whether DD reaches line 06.

A particularly precise question for Peter is therefore:

What rule in the operational semantics of C
prevents the simulated invocation HHH(DD)
at line 03 from returning 0?

If there is such a rule, identify it.

If the answer is merely that HHH starts another simulation of DD, then we
have established one more nesting level.

The same question then applies to the nested HHH invocation.

That missing step is exactly what has to be proved, not declared outside
the permitted subject matter.


4. THE ALLEGED SIPSER ENDORSEMENT

Peter repeatedly quotes Michael Sipser as having agreed to the following words:

If simulating halt decider H correctly simulates its
input D until H correctly determines that its simulated D
would never stop running unless aborted then

H can abort its simulation of D and correctly report that
D specifies a non-halting sequence of configurations.

Read carefully what this actually says.

In schematic form it is:

A -> B

where A contains the crucial premise:

H correctly determines that D would never stop running.

Sipser's agreement with:

A -> B

does NOT constitute agreement with:

A.

And without A, modus ponens cannot be used to obtain B.

That distinction is particularly important here because A is precisely
what Peter is required to establish about HHH.

Of course, IF H has correctly determined that a computation will never
halt, THEN H may correctly report that it will not halt.

The disputed issue is whether Peter's HHH has actually made such a correct determination.

Nothing in the quoted statement says that Peter's particular detector establishes A.

Nothing there endorses his HHH implementation.

Nothing there says that his repeated-CALL criterion proves non-halting.

Nothing there proves that his nested simulation must continue forever.

So there is an invalid transfer of agreement if:

Sipser agrees with A -> B

is presented as though:

Sipser agrees with A

or:

Sipser therefore endorses B for HHH.

He does not, on the basis of the quoted statement.

The crucial antecedent A still has to be proved.


5. THE OTHER INVALID TRANSFER OF AGREEMENT: MY CASE

With statements of mine, Peter has repeatedly made essentially the complementary mistake.

I agreed with an observation we can call A:

A:
applying the C operational semantics produces
the recursive simulation pattern

HHH simulates DD
-> DD calls HHH(DD)
-> HHH simulates DD
-> ...

Peter then takes for granted an additional proposition of the form:

A -> B

where B is something substantially stronger, such as:

this recursive nesting necessarily continues forever,
no nested HHH invocation can return,
and DD therefore cannot reach its final state.

But I have NOT agreed with that implication.

So:

I agree with A

does not permit Peter to conclude:

I agree with A -> B

and consequently does not permit him to claim:

I agree with B.

This is the mirror image of the Sipser problem.

With Sipser:

Sipser accepts A -> B.

Peter behaves as though Sipser therefore accepted A and B
for Peter's HHH.

That is invalid.

With me:

I accepted A.

Peter behaves as though, because HE takes A -> B for granted,
I therefore accepted B.

That is equally invalid.

For clarity:

Case 1:

Person agrees with A.
Peter believes A -> B.
--------------------------------
Peter says person agrees with B.

INVALID.

Case 2:

Person agrees with A -> B.
Person has NOT agreed with A.
--------------------------------
Peter says person agrees with B.

INVALID.

Only this would justify attributing B to the person:

Person agrees with A.
Person agrees with A -> B.
--------------------------------
Person is committed to B.

That is ordinary modus ponens.

The missing agreement cannot simply be supplied by Peter because Peter
himself believes it.

I explicitly told Peter, repeatedly:

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 has therefore been proved correct.

Eventually Peter himself wrote:

I did not realize that you did not mean:

IF HHH keeps simulating
that simulation does not naturally return.

I thought that you were saying the same exact
meaning more verbosely.

Peter therefore explicitly acknowledged that he had misunderstood what I meant.

An initial misunderstanding can happen.

But once the person being quoted has explicitly corrected that misunderstanding, continuing to present the earlier statement as that
person's endorsement of the stronger claim is no longer a reasonable interpretation of that person's position.

Peter is perfectly entitled to argue that my rejection of his inference is WRONG.

He is not entitled to convert that disagreement into my AGREEMENT with the inference.

Likewise, he is perfectly entitled to argue that his HHH satisfies
Sipser's antecedent.

He is not entitled to convert Sipser's agreement with a conditional into Sipser's agreement that HHH satisfies its antecedent.


6. REPRESENTATION VERSUS COMPUTATION

There is another recurring source of confusion worth recording.

Peter emphasizes that the input to HHH is a static finite string -- for example the machine code representing DD.

Fine.

Let:

<DD>

denote that finite representation.

But <DD> and the computation DD described by <DD> are not the same thing.

A static finite string does not:

run forever,
halt,
invoke HHH,
return,
or get aborted.

A COMPUTATION represented by that string can do those things.

There is therefore no contradiction whatsoever between:

<DD> is finite static data supplied as input to HHH

and:

DD, the computation represented by <DD>,
calls HHH(<DD>).

Peter has claimed that:

inputs and callers are mutually exclusive

because inputs are static finite strings whereas callers are executable processes.

That misses the distinction entirely.

Nobody requires the finite representation <DD> itself to become an
executable process.

<DD> is the input.

DD is the computation represented by that input.

DD can call HHH(<DD>).

This distinction between a representation and what it represents is fundamental to the halting problem, not an escape from it.


7. FOR FUTURE PARTICIPANTS

A few recurring formulations are worth translating explicitly:

"The recursive simulation continues
while DD is simulated by HHH."

means at most:

WHILE that recursive simulation continues,
it has not yet returned.

It does NOT establish:

that recursive simulation continues FOREVER.

Likewise:

"HHH keeps simulating DD"

is the disputed proposition if "keeps" means "continues forever".

And:

"DD cannot reach line 06 while being simulated"

is the desired conclusion, not a proof of itself.

So 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:

correctly determines

and ask where Peter proves that his HHH actually satisfies that premise.

When he says nested/repeated simulation proves non-halting, remember the terminating P/F/G/Done counterexample above.

When he calls his conclusion a "simulation invariant", ask for the proof
that the alleged invariant is actually preserved -- in particular, the
proof that the relevant HHH invocation cannot return 0.

When he demands that somebody show how simulated DD reaches line 06, the answer is exactly:

HHH(DD) returns 0
-> Halt_Status = 0
-> condition false
-> line 06
-> return 0

If he declares discussion of that HHH return to be "changing the subject", remember that the HHH call IS line 03 of the simulated DD whose behavior
is supposedly the subject.

And when a counterexample is dismissed as "outside the domain" only after
HHH has returned the wrong answer on it, ask for the independently
specified definition of that domain which existed BEFORE the
counterexample was tested.

Finally, distinguish carefully between:

"I agree with this premise."

"I agree that this implication is valid."

"I agree with this conclusion."

Mathematics allows the conclusion to follow by modus ponens only when BOTH
the premise and the implication have been established.

Peter's own belief in whichever missing part he considers "obvious", "invariant", "categorically impossible", or a "semantic tautology" cannot establish it -- and certainly cannot manufacture somebody else's agreement with it.

Keeping these few points in mind can save future participants a
considerable amount of circular discussion.




--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)