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.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)