Re: Analysis of Flibble’s Latest: Detecting vs. Simulating Infinite Recursion ZFC

Ben Bacarisse <ben@bsb.me.uk> writes:

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

Ben Bacarisse <ben@bsb.me.uk> writes:
[...]

And the big picture is that this can be done because false is the
correct halting decision for some halting computations.  He has said
this explicitly (as I have posted before) but he has also explained it
in words:
>
| When-so-ever a halt decider correctly determines that its input would
| never halt unless forced to halt by this halt decider this halt
| decider has made a correct not-halting determination.

>
Hmm.  I don't read that the way you do.  Did I miss something?
>
It assumes that the input is a non-halting computation ("its input
would never halt") and asserts that, in certain circumstances,
his mythical halt decider correctly determines that the input
is non-halting.
>
When his mythical halt decider correctly determines that its input
doesn't halt, it has made a correct non-halting determination.
It's just a tautology.

>
It would be a tautology but for the "unless..." part.  It does not make
the determination that it does not halt.  It determines that it would
not halt were it not for the fact that the decider (a simulation) in
fact halts it.

Right, so the computation itself is non-halting.  The mythical
"halt decider" is a simulator that, I suppose, can either faithfully
execute the computation (which will take forever if it's non-halting)
*or* partially execute it and stop executing it at some arbitrary
point.  (The latter is of course not a correct full emulation of
the computation.)  The "forced to halt" step is not part of the
computation.

`int main(void) { while (1); }` is non-halting, at least in the C
abstract machine.  The fact that I can kill it by typing Control-C or
pulling the power plug doesn't change that.  If I don't immediately
notice the obvious, I can simulate its execution, letting it iterate
a few times, until I realize that it's never going to halt.  At that
point I can interrupt my simulation and correctly report that the
program does not halt (something I can do for this program, but not for
all programs).

If you don't assume that this "halt decider" is the impossible
thing that olcott claims it is, but rather is a program that can
simulate another program's execution and report one of "halts",
"does not halt", or "I don't know", it seems to me that olcott's
statement is true and unremarkable (though a little convoluted).
It does not of course refute the validity of the existing proofs
that the Halting Problem is unsolvable.

I'm trying to analyze the statement by itself, ignoring the context
of the years of nonsense olcott has posted.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */