• Exactly how the Peter Linz H correctly decides H_Hat

    From olcott@21:1/5 to Ben Bacarisse on Thu Nov 5 21:43:52 2020
    XPost: comp.theory, comp.ai.philosophy, comp.software-eng

    On 11/5/2020 8:50 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    The correctness of any decider or partial decider can only be
    correctly measured against the decision criteria of this decider or
    partial decider.

    "It should do what it should do".

    Any intuition to the contrary is necessarily incorrect.

    "Any idea that is shouldn't do what it should do is wrong".

    All of the halting decisions of a partial halt decider that:
    (a) Executes its input a single state transition at-a-time.

    (b) Stops the execution of all inputs that it decides would not
    otherwise terminate: DOES_NOT_HALT

    (c) Allows the remaining inputs to continue until they terminate:

    You have constrained your partial halt decider here. You have forced all
    the incorrect results into the (b) category (not that that matters).

    Are necessarily correct for every computation that it correctly
    decides to stop and every computation that it does not decide to stop
    that terminates.

    That sounds like it's correct if it's correct. It would be clearer if
    you just said when you permit you partial decider to be wrong. But
    again, it doesn't matter because you consider only one case below.

    Now we apply this principle to the Peter Linz H_Hat:

    void H_Hat(u32 P) // (bottom of page 319)
    if (Aborted_Because_Non_Halting_Behavior_Detected(P, P))
    HERE: goto HERE;

    // Linz calls this H (page 318)
    bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I);

    No. Linz's H is not a partial halting decider. And Linz's H is
    supposed to be a Turing machine, not a function in some pseudo-code with
    a notion of "aborting". And Linz's H has a single string encoding a computation as its input. There are more differences than similarities.

    You should re-phrase the halting problem in terms of your chosen model
    of computation.


    Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

    According to the above definition of a partial halt decider:
    bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I);
    correctly decides halting for the Peter Linz H_Hat

    I think you mean your H_Hat above because Linz's H^ is a Turing machine.
    And H_Hat is not something you can decide halting for (even incorrectly) because it's not a computation. You mean (or should mean) that the
    function with a silly name correctly decides halting for


    i.e. that Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is false if H_Hat(H_Hat) is a halting computation and true otherwise.

    because within this definition of a partial halt decider the invocation of: >> Aborted_Because_Non_Halting_Behavior_Detected(P, P);
    would be infinitely recursive unless the halt decider terminates the
    execution of H_Hat according to clause (b) of this definition.

    That's the least such a naive partial halt decider should do (more sophisticated ones might not need to emulate the given computation at
    all), but it's not enough to get the right answer. You won't be able to
    see that, though, unless you know what the right answer is, and despite
    the fact that you said you did know, I don't think you do. Do you know
    what the right answer is?

    But why do you care? A partial halt decider is allowed to get some
    instances wrong, so why worry about this particular one?

    That I defined a partial halt decider that does correctly decide H_Hat
    when H_Hat is in the Linz specified relation to its halt decider is self evident from the original post.

    To make it clear that H_Hat really is stuck in infinite recursion we
    discard all of the halt deciding of H() and simply DebugTrace(H_Hat,

    void H_Hat(u32 P) // (bottom of page 319)
    if (H(P, P))
    HERE: goto HERE;

    u32 H(u32 P, u32 I)
    return DebugTrace(P, I);

    int main()
    H(H_Hat, H_Hat);

    Copyright 2020 Pete Olcott

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

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