1. Forum
  2. Usenet
  3. COMP.SOFTWARE-ENG

  • Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within in

    From olcott@21:1/5 to Kaz Kylheku on Mon Dec 14 19:34:08 2020
    XPost: comp.theory

    On 12/14/2020 6:49 PM, Kaz Kylheku wrote:
    On 2020-12-15, Richard Damon <[email protected]> wrote:
    On 12/14/20 5:54 PM, olcott wrote:


    The halt decider is inherently a simulator any code that it does not
    simulate is code that it cannot examine.

    False.

    There is NO requirement that a Halt Decider actually run all the code.

    It is allowable to build a decider by pattern matching the code and
    looking at its structure.

    Well, it seems Olcott has a hybrid approach: running the code and doing
    a dynamic pattern match against several trivaial aspects of its behavior rather than static structure. He is presently not concerned with
    building a universal halting decider, so the approach having obvious
    flaws (like succumbing to non-terminating behavior which falls under a pattern that is not detected) isn't a problem.

    The problem is with the claim that the setup refutes the structure used
    in certain halting proofs.

    If/when he reveals why the one instanece of Halts(H_Hat, H_Hat) invoked
    from main() is able to return a value, even though the same Halts(H_Hat, H_Hat) invocation from within H_Hat supposedly doesn't return, it will
    be possible to precisely articulate the fallacy (that obviously exists).

    There is no way that Halts can be a pure function over the inputs denoted by its arguments, as declared in the C language, yet exhibit different
    behaviors on different invocations from different places in the same
    program, when the same arguments are given.

    The problem is that this is a requirement.

    If Halts isn't a pure function, it isn't a viable decider. A halting
    decider is a specific Turing machine: one machine, which denotes a set
    of calculation steps, and only that set, always. It corresponds to a
    pure function being applied to arguments. A non-function substituted for Halts cannot refute a proof which specifically requires that Halts be a function.

    If Halts is shown to be a pure function, but not (just) a function of
    its declared inputs (i.e. it has tacit inputs not immediately visible in
    the higher level language), then it will be shown that the two calls to
    Halts are using different values for these hidden inputs. Therefore, the claim is again not valid: main() calls one decider function, whereas
    H_Hat calls a different one.


    I have explained the difference between these two computations many times:

    int main()
    {
    Halts((u32)H_Hat, (u32)H_Hat);
    H_Hat((u32)H_Hat);
    }

    It seems that people simply don't want to understand.

    The difference between these two computations is the last gasp excuse
    that people can use to posit that I may be incorrect.

    --
    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)
  • From Kaz Kylheku@21:1/5 to olcott on Tue Dec 15 09:36:29 2020
    XPost: comp.theory

    On 2020-12-15, olcott <[email protected]> wrote:
    I have explained the difference between these two computations many times:

    That's nice; you're not responding to the content of any of my points.

    int main()
    {
    Halts((u32)H_Hat, (u32)H_Hat);
    H_Hat((u32)H_Hat);
    }

    1. Those are not the two I'm talking about, but since our particular H_Hat((u32)H_Hat) immediately calls Halts((u32)H_Hat, (u32)H_Hat), how
    can there be a legitimate difference between those two?

    2. I'm talking about both main() and H_Hat both making a call to Halts((u32)H_Hat, (u32)H_Hat). One returns, producing a value which
    indicates that the ... other one doesn't return? What?

    How can exactly the same procedure both return and not return, unless it
    isn't a pure function, or else not a function of just those arguments
    that are apparent in the higher level language?

    It seems that people simply don't want to understand.

    The difference between these two computations is the last gasp excuse
    that people can use to posit that I may be incorrect.

    If you want to prove things by hacking, you have to be prepared for
    such at thing showing you wrong. I'm surprised you wouldn't be prepared
    for that, as a long-time programmer. You know, one flipped bit brings
    down the show, and all that. Likewise, in logic, one flawed step in a
    chain of inferences, and the argument is toast.

    --
    TXR Programming Language: http://nongnu.org/txr

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