• =?UTF-8?Q?Re=3a_Clarification_of_Linz_=c4=a4_Description_=28V2=29?=

    From olcott@21:1/5 to Ben Bacarisse on Wed Sep 29 18:19:10 2021
    XPost: comp.theory, sci.logic, sci.math

    On 9/29/2021 5:48 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    The following simplifies the syntax for the definition of the Linz
    Turing machine Ĥ, it is now a single machine

    It always was.

    with a single start state.

    All TM's have a single start state.

    A simulating halt decider is embedded at Ĥ.qx.

    This is not "clarifying" but restricting. Linz uses Ĥ to refer to any
    TM constructed in a certain way.

    It has been annotated so that it only shows Ĥ applied to ⟨Ĥ⟩,
    converting the variables to constants.

    You don't know what at least two of those these words mean. The result
    is a sentence that is "not even wrong".

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
    if the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ reaches its final
    state. (Halts)

    The correct annotation is the one in Linz: "if Ĥ applied to ⟨Ĥ⟩ halts".

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
    if the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ never reaches its
    final state. (Does not halt)

    The correct annotation is the one in Linz: "if Ĥ applied to ⟨Ĥ⟩ does not
    halt".

    You must deny what Linz says because you are not talking about halt
    deciders. You are trying to pretend that Linz was talking about
    deciders for your other problem:

    This definition of halting circumvents the pathological self-reference
    error for every simulating halt decider:

    An input is decided to be halting only if ...

    On that basis:
    Ĥ(<Ĥ>) ⊢* Ĥ.qn
    H(<Ĥ>,<Ĥ>) ⊢* H.qn

    You don't get to say what halting is. It is already well-defined. Any definition that provides a basis for H rejecting a computation that is
    finite is garbage.


    1----2-----3-----4--5-----6
    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

    (A) The Linz proof is about whether or not (4) halts on its input (5).
    When the halt decider at Ĥ.qx is a simulating halt decider the Linz
    proof becomes about whether or not the simulation of (4) halts on its
    input (5).

    (B) The Linz proof is not about whether or not (1) halts on its input (2).

    Although it may be over your head because it is very very difficult
    to understand (A) and (B) are distinctly different computations that can
    have opposite final states without contradiction.



    --
    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)
  • From olcott@21:1/5 to All on Thu Sep 30 18:21:53 2021
    XPost: comp.theory, sci.logic, sci.math

    On 9/30/2021 5:55 PM, André G. Isaak wrote:
    On 2021-09-30 16:12, olcott wrote:

    Because of a critique of my work in another forum I have discovered
    that the halt status that H1(P,P) reports is consistent with the
    behavior of int main() { P(P); }

    But how does this address the Linz proof then? You've derived your P
    from H, not from H1. So all that matter with respect to the Linz proof
    is what *H*(P, P) returns. That some other decider H1, from which P is
    *not* derived, can correctly decide P(P) has no bearing on Linz's claim.
    H1 cannot decide P1(P1) where P1 is derived from H1 in the same way that
    P is derived from H.


    H(P,P) is correct and H1(P,P) is correct.

    And your proposed 'best of three' test won't work either, since it will
    be possible to derive a BestOfThree_Hat construction from your
    BestOfThree routine which your BestOfThree routine won't be able to decide.

    You don't seem to grasp that Linz is *not* claiming that there are computations whose halting status cannot be decided.

    He is claiming that H does not exist:
    The contradiction tells us that our assumption
    of the existence of H, and hence the assumption
    of the decidability of the halting problem,
    must be false. (Linz 1990:320).

    https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
    Not only does the Linz H exist it gets the correct answer and this
    answer is consistent with the behavior of Ĥ applied to ⟨Ĥ⟩

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

    He is claiming that
    there cannot be a *universal* halt decider because for every purported
    halt decider one can construct a TM which that specific halt decider
    cannot correctly decide.

    André




    --
    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)
  • From olcott@21:1/5 to All on Thu Sep 30 20:27:59 2021
    XPost: comp.theory, sci.logic, sci.math

    On 9/30/2021 8:07 PM, André G. Isaak wrote:
    On 2021-09-30 18:54, olcott wrote:
    On 9/30/2021 7:39 PM, André G. Isaak wrote:
    On 2021-09-30 18:26, olcott wrote:
    On 9/30/2021 7:18 PM, André G. Isaak wrote:
    On 2021-09-30 17:21, olcott wrote:
    On 9/30/2021 5:55 PM, André G. Isaak wrote:
    On 2021-09-30 16:12, olcott wrote:

    Because of a critique of my work in another forum I have
    discovered that the halt status that H1(P,P) reports is
    consistent with the behavior of int main() { P(P); }

    But how does this address the Linz proof then? You've derived
    your P from H, not from H1. So all that matter with respect to
    the Linz proof is what *H*(P, P) returns. That some other decider >>>>>>> H1, from which P is *not* derived, can correctly decide P(P) has >>>>>>> no bearing on Linz's claim. H1 cannot decide P1(P1) where P1 is
    derived from H1 in the same way that P is derived from H.


    H(P,P) is correct and H1(P,P) is correct.

    So you're saying they both return true? If so, why on earth do you
    *need* H1? Why bring it up at all?


    H(P,P) correctly determines that its input never reaches its final
    state whether or not H aborts the simulation of this input.

    H1(P,P) correctly determines that its input reaches its final state.

    They have the *same* input. Therefore they cannot both be correct
    unless they give the same answer. You can't have one of them claim
    that P(P) never reaches its final state and the other say that P(P)
    does reach its final state *and* claim they are both correct.

    That's Trump Logic.

    André



    You have to wait until finish converting functions H1 and H to pure
    functions. They do derive this result now yet it is possible that this
    result is an artifact of their requirement of static local data to
    derive these results.

    If it works out like preliminary analysis indicates a pair of
    functions with identical machine code and identical inputs really do
    have different output because the input to H(P,P) calls H and the
    input to H1(P,P) calls H (thus does not call H1).

    Your statement is entirely incoherent. If H(P, P) and H1(P, P) give
    different results then either:

    (A) one is wrong.

    or

    (B) they are not computing the same function, in which case at most
    *one* of them can actually be deciding the halting function.

    You understand that the halting function (which maps computations to
    halting values) is a mathematical object which exists independently of
    any Turing Machine or algorithm and has a fixed mapping from
    computations to {true, false}, right?

    André


    It will continue to be impossible for you to overcome your false
    assumptions until you see that:

    (a) H1(P,P) correctly reports that its input reaches its final state.

    (b) H(P,P) correctly reports that its input NEVER reaches its final
    state (whether or not it aborts the simulation of this input).

    (c) Both H1 and H are pure functions and have identical machine code.

    In computer programming, a pure function is a function that has the
    following properties:

    (1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable
    reference arguments or input streams).

    (2) The function application has no side effects (no mutation of local
    static variables, non-local variables, mutable reference arguments or input/output streams).

    https://en.wikipedia.org/wiki/Pure_function


    --
    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)
  • From olcott@21:1/5 to Mike Terry on Fri Oct 1 09:36:16 2021
    XPost: comp.theory, sci.logic, sci.math

    On 10/1/2021 9:12 AM, Mike Terry wrote:
    On 01/10/2021 01:54, olcott wrote:
    On 9/30/2021 7:39 PM, André G. Isaak wrote:
    On 2021-09-30 18:26, olcott wrote:
    On 9/30/2021 7:18 PM, André G. Isaak wrote:
    On 2021-09-30 17:21, olcott wrote:
    On 9/30/2021 5:55 PM, André G. Isaak wrote:
    On 2021-09-30 16:12, olcott wrote:

    Because of a critique of my work in another forum I have
    discovered that the halt status that H1(P,P) reports is
    consistent with the behavior of int main() { P(P); }

    But how does this address the Linz proof then? You've derived
    your P from H, not from H1. So all that matter with respect to
    the Linz proof is what *H*(P, P) returns. That some other decider >>>>>>> H1, from which P is *not* derived, can correctly decide P(P) has >>>>>>> no bearing on Linz's claim. H1 cannot decide P1(P1) where P1 is
    derived from H1 in the same way that P is derived from H.


    H(P,P) is correct and H1(P,P) is correct.

    So you're saying they both return true? If so, why on earth do you
    *need* H1? Why bring it up at all?


    H(P,P) correctly determines that its input never reaches its final
    state whether or not H aborts the simulation of this input.

    H1(P,P) correctly determines that its input reaches its final state.

    They have the *same* input. Therefore they cannot both be correct
    unless they give the same answer. You can't have one of them claim
    that P(P) never reaches its final state and the other say that P(P)
    does reach its final state *and* claim they are both correct.

    That's Trump Logic.

    André



    You have to wait until finish converting functions H1 and H to pure
    functions. They do derive this result now yet it is possible that this
    result is an artifact of their requirement of static local data to
    derive these results.

    Or some other form of cheating such as a function taking its own
    address, and varying its processing according to that address.

    (I suggested this was all that was going on a couple of weeks ago, but
    you neither confirmed nor denied that.  Almost as though you actually
    don't understand /yourself/ what's going on.  (Surely that cannot be...!))

    I don't reply to nonsense.



    If it works out like preliminary analysis indicates a pair of
    functions with identical machine code and identical inputs really do
    have different output because the input to H(P,P) calls H and the
    input to H1(P,P) calls H (thus does not call H1).

    Of course an /unrestricted/ x86 program can do that - all it has to do
    is look at its own address and behave differently according to that
    address.  (Like your H/H1 routines.)  Or cheat with global variables etc..


    The halting theorem counter-examples present infinitely nested
    simulation (non-halting) behavior to every simulating halt decider.

    When the input P to a simulating halt decider H1 does not call this same decider and instead calls another different decider H, then infinitely
    nested simulation is not specified for H1(P,P) as it is for H(P,P).

    If you are concerned with saying things of relevance to TMs and Linz's
    proof, you need to limit your C code to doing things that directly
    correspond with what TMs can do.

    Yes that was my biggest challenge. I didn't even know the criteria for
    that even though Kaz gave me this criteria months ago. After carefully
    checking and double checking this criteria seems sufficient:

    In computer programming, a pure function is a function that has the
    following properties:[1][2]

    (1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable
    reference arguments or input streams).

    (2) The function application has no side effects (no mutation of local
    static variables, non-local variables, mutable reference arguments or input/output streams).
    https://en.wikipedia.org/wiki/Pure_function

    Otherwise the relationship between
    your computing model and TMs will become distorted and the conclusions
    you want to draw from your program's behaviour to TM behaviour may
    simply not apply.

    I know that last paragraph is WAAAAAY over your head (computation
    models?  too abstract!) so you will just ignore it.  Or perhaps spray
    your "Objection Begone!" Turing-equivalence spray at it, which never
    works for you. :)

    Anyway, you need to work out /why/ copying an algorithm can produce
    different behaviour in the copy, and STOP DOING IT!!  (Just like you
    seem to have recognised that non-pure functions are to be avoided.  I'm
    not sure whether using your own machine code address breaks the "pure function" rules per se, but the effect on your efforts is the same so it doesn't really matter.)


    Mike.

    My redesign meets all of the above pure function criteria.

    It really is the case that a pair of pure functions with identical
    machine code will have different behavior on the same input when this
    input calls one of these functions in pathological self-reference and
    not the other. Identical functions, identical input, differing
    relationships between the functions and their input.

    --
    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)
  • From Jeff Barnett@21:1/5 to olcott on Fri Oct 1 10:45:12 2021
    XPost: comp.theory, sci.logic, sci.math

    On 10/1/2021 8:36 AM, olcott wrote:


    I don't reply to nonsense.


    You do very frequently. You have written messages "in reply to" your own messages more than any other (sub)human alive to day or in the past for
    that matter. Your nonsense and repetitive behavior reminds me of a
    neurotic chimpanzee at our local zoo. It hurts to watch. The Guinness
    Book of World Records is holding a place for you in this regards as well
    as several other categories. Be proud son/daughter; be proud.
    --
    Jeff Barnett

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Jeff Barnett on Fri Oct 1 12:04:44 2021
    XPost: comp.theory, sci.logic, sci.math

    On 10/1/2021 11:55 AM, Jeff Barnett wrote:
    On 10/1/2021 10:27 AM, Andy Walker wrote:
    On 01/10/2021 15:12, Mike Terry wrote [to PO, of course]:
    Of course an /unrestricted/ x86 program can do that [...]
    If you are concerned with saying things of relevance to TMs and
    Linz's proof, you need to limit your C code to doing things that
    directly correspond with what TMs can do. [...]

         I think it is misleading to talk about what TMs can do as
    thought they are interestingly different from what x86 programs or
    any real computer can do.  An x86 computer /is/ a FSM with extra
    storage;  in other words, a TM.  We tend to write rather simple
    TMs to illustrate points, but there is no reason why it should
    not have 2^N states, where N is rather large [the number of bits
    in your computer].  "Taking the address of a function" is not
    "difficult" with a TM, just rather tedious.

         There is no reason why someone [I'm not volunteering!]
    should not write a C compiler the target of which is recognisably
    a TM.  It's just going to be rather complicated.  [Probably easier,
    AAMOF, to write a microcode as a TM, and describe real computers
    in terms of that microcode.  In the 1930s, that would have seemed
    like magic, but it is how many/most modern computers work.]

         That's why I think people are barking up the wrong tree
    when complaining that PO writes C code that is "not a function".
    It doesn't matter.  It just means that the "hat" construction
    is more complicated than PO claims, inc all the states [etc] of
    the FSM, inc "hidden" variables.  The real errors lie elsewhere.
    I think what people are trying to say and may be saying badly is that
    the set of things that can influence an execution must all be considered
    part of that execution. Trivial but important. Said another way apropos
    to the current conversation is that when you propose something to play
    the role of the Linz H, the definition of that something must include everything that influences its execution. PO doesn't do that. 'It' also
    keeps the piece he calls H from being function- or computation-like. One
    of the "rules" of software reasoning is that one must carefully delimit
    the boundaries of what one is talking about. This basic guideline has
    been ignored into oblivion.

    It is very difficult to confirm that a [computable function] https://en.wikipedia.org/wiki/Computable_function#Characteristics_of_computable_functions

    Must be a [pure function]
    https://en.wikipedia.org/wiki/Pure_function

    When no official source say this.

    None-the-less my partial halt deciders {H1, H} are being transformed
    into [pure functions] that take finite string inputs. Also my C/x86
    equivalent P of the Linz Ĥ will copy its input so that it more closely conforms to the Linz Ĥ.

    --
    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)
  • From olcott@21:1/5 to Andy Walker on Fri Oct 1 15:23:45 2021
    XPost: comp.theory, sci.logic, sci.math

    On 10/1/2021 3:09 PM, Andy Walker wrote:
    On 01/10/2021 17:55, Jeff Barnett wrote:
    [I wrote:]
         That's why I think people are barking up the wrong tree
    when complaining that PO writes C code that is "not a function".
    It doesn't matter.  It just means that the "hat" construction
    is more complicated than PO claims, inc all the states [etc] of
    the FSM, inc "hidden" variables.  The real errors lie elsewhere.
    I think what people are trying to say and may be saying badly is that
    the set of things that can influence an execution must all be
    considered part of that execution. Trivial but important. [...]

        Absolutely.  IOW, the "hat" construction is still possible,
    but is not the simplistic version that PO presents.

        [FTAOD, although I was replying to one of your posts, my
    article wasn't "aimed" at you, but at the whole way this "debate"
    has been going.  It's too easy to get sucked in to PO's way of
    "thinking".]



    The whole basis of my rebuttal of the halting problem proofs:

    The halting theorem counter-examples present infinitely nested
    simulation (non-halting) behavior to every simulating halt decider.

    How the simulating halt decider detects that an input is presenting
    infinitely nested simulation is merely an implementation detail.

    --
    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)