1. Forum
  2. Usenet
  3. COMP.THEORY

  • Halting Problem Refuted!

    From Mr Flibble@21:1/5 to All on Sun Feb 16 13:13:21 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.

    /Flibble

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to Mr Flibble on Sun Feb 16 17:49:01 2025
    On 16/02/2025 13:13, Mr Flibble wrote:
    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": [...].

    You can't, of course, "refute" a problem; you can [perhaps]
    solve it, or [perhaps] prove it insoluble, or perhaps even both, if
    your proofs depend on inconsistent axioms or are incorrect. You may
    be able to refute a conjecture, or an attempted proof. But you knew
    that. Also, of course, there is no "impossible" [or "pathological"]
    actual program, only proofs that programs with certain properties
    cannot be constructed. But you knew that, too. With hindsight, one
    might wish that Strachey had been more careful with his language.

    Obviously my idea necessitates extending the definition of a halt
    decider: [...].

    Obviously.

    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.

    The only "great minds" to have mulled over the assorted proofs
    of the [insolubility of the] HP and its relatives for decades are the
    regular writers of articles here. The rest of us learn about these
    things, typically as a small part of a CS degree or similar, go through
    a brief period of "But surely you can try ...?" and then move on. But
    one of those GMs enjoys the attention and the rest simply cannot resist
    feeding the one.

    Oh, and just in case you were serious, yes, of course there is something obviously wrong with your "idea", which you will easily find
    out if you try to implement it.

    [Somewhat on the other hand, we had an MSc student once who got
    a job with a software house. He popped in a couple of years later.
    "How's it going?" "Oh, very well. I'm writing a program to do {X}."
    "But don't you know that {X} is equivalent to the HP?" "Oh, yes, but
    my boss wants me to do it, even though we both know it's impossible."
    Fast forward a couple of years, and he pops in again. "Given up on
    {X} now?" "Oh, no, I'm making good progress." Couple of years later;
    "Almost finished. There's just one case left to tackle." Rinse and
    repeat. Eventually, I believe it went to market as an incomplete but
    slightly useful diagnostic tool (which everyone always knew was doable
    with a few weeks of development).]

    --
    Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Schubert

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