On 22/05/2025 06:41, Richard Heathfield wrote:

On 22/05/2025 06:23, Keith Thompson wrote:

Richard Heathfield <[email protected]> writes:

On 22/05/2025 00:14, olcott wrote:

On 5/21/2025 6:11 PM, Richard Heathfield wrote:

[...]

Turing proved that what you're asking is impossible.

That is not what he proved.

Then you'll be able to write a universal termination analyser that can
correctly report for any program and any input whether it halts. Good
luck with that.

Not necessarily.

Of course not. But I'm just reflecting. He seemed to think that my inability to write the kind of
program Turing envisaged (an inability that I readily concede) is evidence for his argument. Well,
what's sauce for the goose is sauce for the gander.

Even if olcott had refuted the proofs of the
insolvability of the Halting Problem -- or even if he had proved
that a universal halt decider is possible

And we both know what we both think of that idea.

-- that doesn't imply
that he or anyone else would be able to write one.

Indeed.

I've never been entirely clear on what olcott is claiming.

Nor I. Mike Terry seems to have a pretty good handle on it, but no matter how clearly he explains it
to me my eyes glaze over and I start to snore.

Hey, it's the way I tell 'em!

Here's what the tabloids might have said about it, if it had made the front pages when the story broke:

COMPUTER BOFFIN IS TURING IN HIS GRAVE!

An Internet crank claims to have refuted Linz HP proof by creating a
Halt Decider that CORRECTLY decides its own "impossible input"!
The computing world is underwhelmed.

Better? (Appologies for the headline, it's the best I could come up with.)

Mike.

[...] He has rarely, if ever, stated his claims clearly enough
for anyone to be sure what he's claiming.� Of course I could
have missed something, since I've read less than 1% of what he
writes.

He has been urged to summarise his complete argument on a Web page. Several times, in fact. He
generally responds with a nonsensical copy and paste.

But if you took everything he's posted here and combined it into
a single text file, I'll bet it would compress *really* well.

;-)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/05/2025 19:37, Keith Thompson wrote:

Ben Bacarisse <[email protected]> writes:

Mike Terry <[email protected]> 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.

You're reading it the way most people would, and in the way I said Sipser would be interpreting the
oft-quoted "Sipser quote". I don't think you've missed anything particularly.

I suppose Ben quoted PO saying this, because PO /uses/ it to justify that a particular /halting/
computation will never halt, PO's HHH simulates DDD (which halts) but before DDD halts it spots a
pattern in the simulation, and announces non-halting. "Eh?" I hear you say! PO claims HHH has
"correctly determined that DDD would never halt" and so is correct to decide non-halting. His
"proof" that it is right to decide non-halting is his "when-so-ever.." quote, which broadly matches
the Sipser quote.

So the problem is not so much the "when-so-ever.." words themselves [or the words of Sipser's
quote], but understanding how PO is so thoroughly misinterpreting/misapplying them. How can PO
believe HHH has "correctly determined the DDD will never halt" when DDD demonstrably halts?

Rather that try to explain that, I'll suggest that it really doesn't matter exactly /why/ PO is
confused. It's enough that his claims are obvious nonsense, and readers of a certain level see this
pretty much straight away. People who post corrections and try to help PO /see/ his mistakes and
change his mind are completely wasting their time, although of course it's entirely theirs to waste!

As to whether Ben's PO quote was helpful supporting material for his remark that PO believes it's
right to decide non-halting for certain halting computations - you'll have to decide that. [PO
/does/ think it's right to decide non-halting for certain halting computations, although PO's
conception of halting does not match yours or mine.]

This kind of determination can be made in specific cases (but of
course not in general). A simple program like `int main(void)
{ while (1); }` is non-halting. If I run it, it will never halt
unless I force it to halt, e.g. by typing Control-C or pulling the
power plug.

(I'm assuming that "when-so-ever" means the same as "when".)

Yeah, one of PO's affected wordings that he likes. I read it as "whenever".

If you likewise ran PO's DDD(DDD) you would not have time to enter ^C because it would complete in
short order. His HHH which is simulating the computation can get its abort in, because the
simulation is step-by-step, and after each step HHH gets to choose whether to continue or abort the
simulation.


Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 24/05/2025 01:26, Ben Bacarisse wrote:

Mike Terry <[email protected]> writes:

On 23/05/2025 19:37, Keith Thompson wrote:

Ben Bacarisse <[email protected]> writes:

Mike Terry <[email protected]> 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.

You're reading it the way most people would, and in the way I said Sipser
would be interpreting the oft-quoted "Sipser quote". I don't think you've >> missed anything particularly.

Maybe it makes less sense out of the context it was posted in. This was
when he was being less obtuse. The computation in question only halts because it is halted by the decider on which it is built. It is a
halting computation, but according to PO it can reported as not halting because of what would happen if it were not halted by the decider from
which it is derived.

"The computation in question only halts because it is halted by the decider on which it is built."

That is presumably you speaking in PO's voice, but my first reading was as you saying it!

Of course, the computation in question [DDD(DDD)] is at no point "halted" by anything, and halts
quite happily all on by itself!

Subsequent wordings have all been about hiding this. Just prior to this wording was the even more explicit claim that non-halting is correct
because of what "would happen if line 15 were commented out". It's
always been about what would be the correct decision were the
computation not what it actually is.

Yes, current posters are right on top of that, calling it out as "changing the input". I'm not sure
PO realises he is changing the input, and if he does, whether he understands /why/ that is
completely out of order. PO has recently started talking about what happens when we hypothetically
"change the HHH/DDD input /pair/ " so that makes me think he does now explicitly realise that's
what's going on, but not why it's a mistake.

As ever, pointing it out to PO, however explicitly and clearly, has no effect on what PO believes.


Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 24/05/2025 01:36, Keith Thompson wrote:

Ben Bacarisse <[email protected]> writes:

Keith Thompson <[email protected]> writes:

Ben Bacarisse <[email protected]> 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.

No no no, it halts! (Assuming we're discussing the computation DD() with PO's code.)

Ben's wording is as bad as PO's. In fact Ben just copies PO's wording without explaining or
clarifying anything.

I feel that the quickest way for you to get everything straight in your head would be to actually
trace through yourself (line by line) what computations HHH(DD) and DD() do at a high level
(pseudocode, not x86 instructions). That way you'll see for yourself that DD() halts, and HHH(DD)
decides non-halting. [I'd guess it might take you 20 minutes, but how long have you already spent
posting??] If you're not clear on what you would trace for HHH, ask and I'll concoct some
high-level pseudocode for you.

Your interpretation of the statement as a tautology is how everybody but PO reads the statement.
Here is what you say:

-----

If 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.

-----

[Bear in mind that with PO's HHH(DD), it /incorrectly/ determines that its input doesn't halt. But
sure, the statement as you're reading it is a tautology. That tautology just doesn't apply to PO's
HHH(DD).]

So how does PO's reading differ? The problem is with your phrase "its input doesn't halt". That's
fine wording, directly invoking the /definition/ of "halt", which most people understand, but PO
CAN'T DO ABSTRACT. In his head he has replaced the definition with something he /can/ cope with -
some "concrete" procedure he can imagine performing, involving simulations and amended code. So
what exactly is this concrete procedure PO imagines?

PO imagines /changing the code of HHH/ so that it doesn't abort. Then if "DD" would never halt that
means HHH is right to decide non-halting. AND FINALLY THE PROBLEM: DD calls HHH, so when PO
imagines changing the code of HHH, he is also imagining changing the behaviour of HHH's input (DD)
so the new DD calls the new HHH which doesn't abort! In case it needs spelling out, that's wrong,
because HHH was asked to decide halting for the specific (fixed) input DD, and the behaviour of that
input is to call the specific (fixed) HHH. We may consider how /that input/ might be decided by a
modified decider, but if we switch to examining a /new/ input with different behaviour that has no
bearing on DD's halting status.

With less words (probably clearer):
- HHH(DD) is asking HHH to decide halting of DD()
HHH and DD are actual programs with fixed code. (and DD halts)
- PO imagines changing HHH to HHH2 which doesn't abort.
This also changes DD behaviour so it calls the new HHH2 instead of HHH.
We'll call this new DD DD2.
- He considers HHH2(DD2) and concludes that HHH2 will never end its simulation of DD2.
[Indeed, computation DD2() does not halt.]
- So based on your/Sipsers wording [but with his own interpretation as above]
he concludes "It is correct for HHH to decide DD never halts".
[In fact DD does halt. It is obviously DD2 that never halts.]

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.

Perfect.

`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).

Perfect.

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.

With your interpretation the statement is indeed true but unremarkable. That is effectively what
Sipser agreed to (IMO). We can imagine a correct partial simulating halt decider applying your
interpretation to report a tight loop as non-halting.

BUT PO's interpretation of the statement which I've tried to explain above [all the stuff about
changing both HHH /and/ its input DD] is what he is using now to justify his claim that his specific
HHH correctly decides its corresponding "HP counterexample" input DD. If this latter claim were
true, that /would/ refute the validity of the Linz HP proof.

So sure, you can say the statement is a tautology, but PO made that statement and his interpretation
of what it means is far from your tautology.

HTH (if only in sending you off on a good night's sleep!)
Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 24/05/2025 22:40, Keith Thompson wrote:

Mike Terry <[email protected]> writes:

On 24/05/2025 01:36, Keith Thompson wrote:

Ben Bacarisse <[email protected]> writes:

Keith Thompson <[email protected]> writes:

Ben Bacarisse <[email protected]> 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.

No no no, it halts!

What halts?

(Assuming we're discussing the computation DD() with PO's code.)

No, I'm not going to assume that. *All* I'm talking about is olcott's statement:

| 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.

I'm not trying to make it consistent with anything else olcott has
written. DD() is irrelevant to what I'm talking about.

As I wrote before, let H be the "halt decider" and let I be its input
(which represents a computation). I by itself does not halt. I-simulated-by-H may halt if H forces it to halt.

H might be a simulator, or it may just monitor the execution of I with
the ability to halt it. H is not a pure simulator; it does not always
fully simulate the execution of I.

H is given the task of determining whether I is a halting computation or
not (a task that is not possible in all cases, but is certainly possible
in some cases).

Fair enough.

Your interpretation of Olcott's statement is indeed a tautology. That tautology is not very
interesting, and most people would interpret the statement in the same as you (and me).

PO's interpretation of the statement is wrong, but that doesn't interest you - he said the words and
the words are correct in some absolute sense even if PO does not understand that sense, and is
thinking of something different. PO made a true statement!

Interestingly, you're doing what PO does, sort of - he says the words mean what /he/ says they mean,
and that meaning justifies one of his false claims. He supports this claim by saying Sipser agreed
with the words, even though it's clear Sipser's agreement was with a different interpretation of
those words.

<PO speaking>
But hey, Sipser "agreed with those words"! Sipser just didn't appreciate the consequence of their
true meaning [aka PO's interpretation]. :)
</PO speaking>

[...]

So sure, you can say the statement is a tautology, but PO made that
statement and his interpretation of what it means is far from your
tautology.

Sure, he does that.

My overall point, I suppose, is that if people are going to argue with olcott, if he happens to make a true statement it's not helpful to argue
that its false.

I'm all for that - I'd go further to say that I champion that point of view. But if PO makes a
statement which he intends to mean XXX and XXX is false, has he made a true statement just because
your interpretation of the same statement is YYY, different from XXX, and YYY happens to be true?

In any case, I don't think anyone would disagree with your interpretation of the statement being a
tautology... Certainly not me. (I think that's all that's to be said on this.)


Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)