Re: Branching Simulating Halt Decider

On 5/10/25 12:10 AM, Mr Flibble wrote:

A Branching Simulating Halt Decider is my idea, from August, 2022:
 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":
 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.
 /Flibble

First, it doesn't "refute" the Halting Problem proofs, as it isn't answering the Halting Problem at all, but something just sort of related. The Halting Problem is about a machine that always returns *THE* correct answer about the behavior of the PROGRAM represented to it. This alternate problem has to be something different, as either it is saying that there are two possible ansser the machine can give (the actual behavior, or an "I d0n't know", as the input as an actual program calling the decider as an actual program will either Halt or Not.).
It might also be talking about some "strange" alternate system where our elements aren't actually required to be "Programs" as defined by the classical theory, but some strange not quite complete programs that get completed at use when they get paired with another fragment.
Your descriptiom of the method also complicates things a lot by trying to add a new way that only some "programs" can answer, the "signalling". Computation Theory just has algroithms and data, and the algorithm when applied to the data will either just faill to halt, or halt an produce an answer. For Turing Machines, this answer can be in the state the machine stopped at and/or the contents of the tape it produced. Fundamental to the system, is that we can then build other programs from these program pieces and use that output as their input, and thus your sNaP signal needs to be "just an output" that can be processed.
Next, You are trying to avoid the two answer problem by implying that the "pathological input" won't halt or not halt, but if the decider and the input are programs, then it MUST do one or the other, because when we run the "program" described by the input, it will use the decider to get the answer and then do SOMETHING after that, which will either halt or never halt. The only way to get this as something different is to admit you aren't working on programs, but now need to define what you are actually working on, and if such a thing has any actual use.
Lastly, if we are working with something at least close to programs, so the input will either halt or not, but sometimes we allow the decider to not have to get the right answer, we really need to try to limit under what conditions the decider can use that last answer, or the problem becomes trivial. Part of the problem is that the term "Pathological Input" hasn't been well defined except as a single esample (and examples are not definitions). For instance, if we DID prepare the input program by the original specifications, and it included a copy of the decider, and not just called the same code as the original decider, is that pathological? What if we make small changes to the code? Totally re-wrote it but created an alternate version that alsways gives the same answer?
It turns out that it is just as impossible to always detect that last case as it was to detect halting, it may require the spending of unbounded time to determine it.
So, it might be able to become an interesting problem to discuss, but only once you give up the idea that it is a refuation of the halting problem, but look at it as a new problem.