Re: Simulating Halt Decider Copyright 2022 Mr Flibble

On 2025-03-02 03:40:31 +0000, olcott said:

On 3/1/2025 8:33 PM, Mr Flibble wrote:

Hi!
 I have an idea for a signaling simulating halt decider that forks the
simulation into two branches if the input calls the halt decider as
per [Strachey 1965]'s "Impossible Program":
 

 The signalling aspect that forks is your idea.
 It is established all over the place for
many years that "simulating halt decider" is my idea.
 

void P(void (*x)())
{
if (H(x, x))
infinite_loop: goto infinite_loop;
return;
}
 int main()
{
std::cout << "Input halts: " << H(P, P) << std::endl;
}
 When the simulator detects the call to H in P it forks the simulation
into a non-halting branch (returning 0 to P) and a halting branch
(returning 1 to P) and continues the simulation of these two branches
in parallel.
 If the non-halting branch is determined to halt AND the halting branch
is determined to not halt then pathology is detected and reported via
a sNaP (signaling Not a Program) signal (analogous to IEEE 754's
sNaN (signaling Not a Number) signal)
 If EITHER branch is determined to be correctly decided then that will
be the decision of the halting decider.
 Crucially this scheme will handle (and correctly decide) the
following case whereby the result of H is discarded by the input:
 void Px(void (*x)())
{
(void) H(x, x);
return;
}
 Obviously my idea necessitates extending the definition of a halt
decider:
 1) Decider decision is HALTS if input halts.
2) Decider decision is NON-HALTING if input does not halt.
3) Decider rejects pathological input as invalid by signaling sNaP.
 Thoughts?  I am probably missing something obvious as my idea
appears to refute [Strachey 1965] and associated HP proofs which
great minds have mulled over for decades.

A program that on some voaid input does not decide HALTS or NON-HALTING
is not a halt decider and therefore does not refute Strachey's proof.
--
Mikko