1. Forum
  2. Usenet
  3. COMP.THEORY

  • Halting Problem Corrected

    From Mr Flibble@21:1/5 to All on Sat May 17 10:54:05 2025
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to Mr Flibble on Sat May 17 13:14:01 2025
    Mr Flibble <flibble@red-dwarf.jmc.corp> writes:

    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?

    The trouble is that this specification has a pointless third case.
    Since every "input" either halts or does not halt, all inputs are
    covered by your first two cases. There are no computations that don't
    do one or the other.

    You can certainly have an almost-decider, AHD, that detects three cases:

    1) The computations AHD can definitely work out are halting;
    2) the computations AHD can definitely work our are non-halting;
    3) all the others.

    But that's old news. Of course such an AHD could well be very useful
    depending on how good it is, but it's not of any interest from a
    theoretical point of view.

    --
    Ben.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to Mr Flibble on Sun May 18 11:13:09 2025
    On 2025-05-17 10:54:05 +0000, Mr Flibble said:

    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.

    There is no signalling in Turing machines. But that is not important.
    The importan thing is that a partial decider may have three output
    values.

    A partial decider is not a correction to anything. It is a partial
    solution that answers some but not all of the questions that a
    solution is required to answer. A third output enables it to decide
    both some halting and some non-halting machines.

    Your decider can correctly determine that Olcott's DDD halts, unlike
    Olcott's own "decider", Which incorrectly determines that DDD does
    not halt.

    --
    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)