On 21/05/2025 20:28, olcott wrote:This step is impossible.On 5/21/2025 2:06 PM, Richard Heathfield wrote:Who cares what *you're* talking about?On 21/05/2025 19:48, olcott wrote:>
>
<snip>
>Show how to define a D that actually does the opposite>
of what its termination analyzer reports.
The whole point of the proof is that no algorithm can define a universal halt decider.
>
I have NEVER been talking about that.
Um... let's see. You? Probably.
I have only been talking about the ACTUALThe ACTUAL conventional proof of the Halting Problem goes something like this:
conventional proof of the halting problem.
1) assume that it is possible to devise an algorithm that can determine in finitely many steps ascertain whether an arbitrary program applied to arbitrary data does or does not stop.
2) given such an algorithm, imagine incorporating it into a program that ascertains whether a supplied program with supplied data halts, loops if it does, and halts if it doesn't.
It only seemed possible because no one ever
tried to completely encode every detail.
This screwy mistake came about because fools thought
that a halt decider H is supposed to report on the behavior
of the program that itself is contained within rather
than the behavior that its actual input actually specifies.
int main()
{
DDD(); // No HHH can report on the behavior of its caller.
}
3) imagine feeding the program to itself, and we arrive at the contradiction that the program would halt if it didn't but not if it did.--
4) Our reasoning has led us to a contradiction, so we deduce that the only assumption we made, in 1) above, is false. QED.
That, highly paraphrased, is the ACTUAL conventional proof of the halting problem.
Note: no simulation required. There's nothing to simulate; it's a thought experiment, not something you actually do.
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer
| Date | Sujet | # | Auteur | |
| 29 Jun 26 |  … |
Les messages affichés proviennent d'usenet.