1. Forum
  2. Usenet
  3. COMP.THEORY

  • Re: Simulating Halt Decider Copyright 2022 Mr Flibble

    From Mikko@21:1/5 to olcott on Sun Mar 2 11:23:12 2025
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Richard Damon@21:1/5 to olcott on Sun Mar 2 16:11:12 2025
    On 3/1/25 10:40 PM, olcott wrote:
    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.

    Only if you ignore the decades old discussions 0f how simulation can be
    used to detect certain classes of non-halting behavior. Look up the idea
    of detecting infinite loops by running two simulators at a 2 steps to 1
    step ratio.

    I remember that from back when I was in college in the 70s, so not your
    idea.

    All you are doing is proving you don't understand what you are talking
    about.

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