Sujet : Re: DDD simulated by HHH cannot possibly halt (Halting Problem)
De : F.Zwarts (at) *nospam* HetNet.nl (Fred. Zwarts)
Groupes : comp.theoryDate : 08. Apr 2025, 16:31:25
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <vt3fgd$2gu7u$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11
User-Agent : Mozilla Thunderbird
Op 08.apr.2025 om 17:13 schreef olcott:
On 4/8/2025 2:45 AM, Fred. Zwarts wrote:
Op 08.apr.2025 om 06:33 schreef olcott:
On 4/7/2025 3:16 AM, Mikko wrote:
On 2025-04-06 16:12:36 +0000, olcott said:
>
On 4/6/2025 5:27 AM, Mikko wrote:
On 2025-04-05 16:45:28 +0000, olcott said:
>
On 4/5/2025 2:05 AM, Mikko wrote:
On 2025-04-05 06:18:06 +0000, olcott said:
>
On 4/4/2025 3:12 AM, Mikko wrote:
On 2025-04-04 01:27:15 +0000, olcott said:
>
void DDD()
{
HHH(DDD);
return;
}
>
Do you really think that anyone knowing the C
programming language is too stupid to see that
DDD simulated by HHH cannot possibly return?
>
Anyone knowing the C language can see that if DDD() does not halt
it means that HHH(DDD) does not halt. The knowledge that that
means that HHH is not a decider is possible but not required.
>
>
*Perpetually ignoring this is not any actual rebuttal at all*
>
*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination. The
only rebuttal to this is rejecting the notion that
deciders must always halt.
>
Wrong, because a termination analyzer is not required to halt.
>
Why say things that you know are untrue?
>
The term "termination analyzer" is used about programs that do not halt
on every input. There is no strict derfiniton of the term so there is
no requirement about halting.
>
On the first page of https://www.cs.princeton.edu/~zkincaid/pub/ pldi21.pdf
in the first parapgraph of Introduction:
>
For example, termination analyzers may themselves fail to terminate on
some input programs, or ...
>
A termination analyzer that doesn't halt
would flunk every proof of total program correctness.
>
There are no total termination analyzers.
>
Total proof of correctness does not require a halt
decider, it only requires a termination analyzer
with inputs in its domain.
>
Depends on what one wants to prove correct.
>
Often there is no way to determine whether a pariticular termination
analyser can determine about a particular program.
>
>
typedef void (*ptr)();
int HHH(ptr P);
>
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
>
int main()
{
HHH(DD);
}
>
*Simulating termination analyzer Principle*
It is always correct for any simulating termination
analyzer to stop simulating and reject any input that
would otherwise prevent its own termination.
>
>
In this case there is nothing to prevent, because the finite string specifies a program that halts.
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
This stuff is simply over-your-head.
HHH(DD) meets the above: *Simulating termination analyzer Principle*
Anyone with sufficient competence with the C programming language
will understand this.
Everyone with a little bit of C knowledge understands that if HHH returns with a value 0, then DDD halts. But Olcott doen even have that little knowledge, it seems. Therefore, he thinks that the simulation must be aborted because there is something that would prevent the termination. But his dreams are no substitute for logic.
He does not even know whether there is an algorithm that can determine for all possible inputs whether the input specifies a program that (according to the semantics of the machine language) halts when directly executed. At least he does not dare to say.