Re: This function proves that only the outermost HHH examines the execution trace

Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

On 27/07/2024 19:14, Alan Mackenzie wrote:

olcott <polcott333@gmail.com> wrote:

Stopping running is not the same as halting.
DDD emulated by HHH stops running when its emulation has been aborted.
This is not the same as reaching its ret instruction and terminating
normally (AKA halting).

I think you're wrong, here.  All your C programs are a stand in for
turing machines.  A turing machine is either running or halted.  There is
no third state "aborted".  An aborted C program certainly doesn't
correspond with a running turing machine - so it must be a halted turing
machine.

So aborted programs are halted programs.  If you disagree, perhaps you
could point out where in my arguments above I'm wrong.

Aborting is an action performed by a simulator, not the TM being simulated.

OK, so if a simulator aborts the program it's simulating, that program is
still in state running, even though it's a suspended animation which will
never get any further.  The simulator, having aborted the program, then
has no more work to do, so the simulator will be in state halted.  Is
that right?

If we want to count "aborted" as some kind of final status, it will
have to be the status of a specific /PARTIAL SIMULATOR's/ simulation of
a given computation.  That's not a property of the computation itself,
as different partial simulators can simulate the same computation and
terminate for different reasons.  Like HHH(DDD) aborts, while UTM(DDD)
simulates to completion and so the final simulation status is halts.
[Neither of those outcomes contradict the fact that the computation
DDD() halts.]

If some partial simulator halts when simulating a computation [as with
UTM(DDD)] that implies the computation DDD() halts.  But if the
simulator aborts, it doesn't say that much (in and of itself) about
whether the /computation/ halts.  The halting problem statement is not
concerned with simulations or how the simulations end.

Indeed not!

Every time anyone in these PO threads says "halts" it ought to be 100%
clear to everyone whether the computation itself is being discussed, or
whether some simulation final status is intended.  (But that's far from
being the case!)  Since the halting problem is concerned with
computations halting and not how partial simulations are ended, I
suggest that PO explicitly make clear that he is referring to
simulations, whenever that is the case.  It seems reasonable that
readers seeing "halts" with no further clarification can interpret that
as actual computation behaviour, as that is how the term is always used
in the literature.  Same with other terms like "reach"...

So when PO says "DDD simulated by HHH cannot reach its final ret
instruction" is he talking about the computation DDD() [as defined
mathematically], or its simulation by HHH?  He means the latter, but
its far from clear, I'd say!  [I think most readers now have come
around to reading it as a statement about simulations rather than the
actual computation, which totally changes things...]

OK.  Thanks for the explanations!

Mike.

--
Alan Mackenzie (Nuremberg, Germany).