Re: How do computations actually work?

On 5/28/2025 2:13 PM, Fred. Zwarts wrote:

Op 28.mei.2025 om 16:31 schreef olcott:

On 5/28/2025 2:36 AM, Mikko wrote:

On 2025-05-27 15:40:33 +0000, olcott said:
>

On 5/27/2025 3:29 AM, Mikko wrote:

On 2025-05-26 16:40:25 +0000, olcott said:
>

On 5/25/2025 10:46 AM, Fred. Zwarts wrote:

Op 25.mei.2025 om 16:50 schreef olcott:

On 5/25/2025 4:09 AM, Mikko wrote:

On 2025-05-24 15:25:21 +0000, olcott said:
>

On 5/24/2025 2:54 AM, Mikko wrote:

On 2025-05-23 16:04:49 +0000, olcott said:
>

On 5/23/2025 2:09 AM, Mikko wrote:

On 2025-05-23 02:47:40 +0000, olcott said:
>

On 5/22/2025 8:24 PM, Mike Terry wrote:

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

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

Richard Heathfield <rjh@cpax.org.uk> 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.
>

>
There is a key detail about ALL of these proofs
that no one has paid attention to for 90 years.
>
It is impossible to define *AN INPUT* to HHH that
does the opposite of whatever value that HHH returns.

>
That is a key detail about HHH. Your HHH is not a part of those proofs.

>
All of the proofs work this same way.

>
No, they don't. Some proofs derive the same conclusion with an essentially
different approach.
>
However, in spite of the differences, they do share a common fieature:
your HHH is not a part of any of the proofs.

>
All of the conventional proofs of the HP assume that
there is an *input D* that can actually do the opposite
of whatever value that HHH returns.

>
Depends on what you mean by "conventional". If you merely mean proofs
that apply ordinary logic then there are proofs with a different
strategy. If you mean only proofs that use the same strategy that
Turing used then you are closer to the truth. But there is no assumption
about the exstence of such D. Its existence is proven.
>

>
In seems that way until you pay much closer attention.
>
int main()
{
   DDD(); // The HHH that DDD calls cannot report on the
}        // behavior of its caller because it cannot see
          // is caller.
>
Even if HHH could see and report on the behavior of
its caller because its caller is not its input this
too is no good.

>
It seems that way to you, until you pay somewhat closer attention.

>
The HHH(DDD) must report on the behavior that its actual input
actually specified CANNOT BE VIOLATED.

>
Of course it can. In fact HHH does violate that. DDD specifies a halting
behaviour but HHH reports that DDD specifies a non-halting behaviour.
That is a violation of that rquirement.

>
If DDD simulated by HHH stops running for any
reason besides reaching its own "ret" instruction
final halt state THEN DDD HAS NOT HALTED.

>
Irrelevant. The requirement is that a halt decider predicts whether the
complete execution of the computation described by the input will halt.
>

>
Halting is defined as reaching a final state and
terminating normally.

 So, according to this definition, every simulator that aborts after one instruction is correct to report a non-halting program.
 

>
int main()
{
   DDD(); // The HHH that DDD calls cannot
}        // see the behavior of its caller
>
*That is incorrect*
A termination analyzer must report on the basis
of the behavior that its input specifies and does
not give a rat's ass about the behavior of its caller.

 The caller is not of any interest. The analyser must report on the input. In this case the anaylzer is given a pointer to memory as input. This contains the code of DDD. That code has addresses, among others in call instructions, that gives the analyser access to other parts of the memory. In this way the analyser should analyse the whole program, including the code that aborts and halt. If done correctly, it will see that the input specifies a halting program.
 

>
_DDD()
[00002192] 55             push ebp
[00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192
[0000219a] e833f4ffff     call 000015d2  // call HHH
[0000219f] 83c404         add esp,+04
[000021a2] 5d             pop ebp
[000021a3] c3             ret
Size in bytes:(0018) [000021a3]
>
It is a tautology that every input to a simulating
termination analyzer would never stop running unless
aborted specifies a non-terminating sequence of
configurations.

If the input specifies a halting program, such as in this case, this is a vacuous statement. It does not need an abort, because the input already specifies an abort, which makes the simulation halt, if done correctly.

You continue to act as if when you are starving
hungry that the fact you won't be hungry after
you have eaten means that you never have to eat.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer