• Pathological self-reference(Olcott 2004) decider [ Defeating Rice's The

    From olcott@21:1/5 to All on Fri Jul 30 08:46:50 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    int Factorial(int n)
    {
    Output("Factorial(n)",n);
    if (n > 1)
    return n * Factorial(n - 1);
    else
    return 1;
    }

    void Infinite_Recursion(u32 N)
    {
    Infinite_Recursion(N);
    }

    void Infinite_Loop()
    {
    HERE: goto HERE;
    }

    int Simulate(u32 P, u32 I)
    {
    ((int(*)(int))P)(I);
    return 1;
    }

    // H and H2 are partial halt deciders
    u32 PSR_Decider(u32 P, u32 I)
    {
    u32 Input_Halts1 = H((u32)P, (u32)I);
    u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)I);
    Output("Input_Halts1 = ", Input_Halts1);
    Output("Input_Halts2 = ", Input_Halts2);
    if (Input_Halts1 != Input_Halts2)
    return 1;
    return 0;
    }

    void P(u32 x)
    {
    if (H(x, x))
    HERE: goto HERE;
    }

    int main()
    {
    Output("PSR_Decider = ", PSR_Decider((u32)P, (u32)P));
    Output("PSR_Decider = ", PSR_Decider((u32)Factorial, 3));
    Output("PSR_Decider = ", PSR_Decider((u32)Infinite_Recursion, 3));
    Output("PSR_Decider = ", PSR_Decider((u32)Infinite_Loop, (u32)Infinite_Loop));
    }

    Here are the return values proving that Rice has been defeated:
    PSR_Decider((u32)P, (u32)P)==1
    PSR_Decider((u32)Factorial, 3)==0
    PSR_Decider((u32)Infinite_Recursion, 3)==0
    PSR_Decider((u32)Infinite_Loop, (u32)Infinite_Loop)==0



    --
    Copyright 2021 Pete Olcott

    "Great spirits have always encountered violent opposition from mediocre
    minds." Einstein

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