• Re: Refuting the HP proofs (adapted for software engineers)[ Mike Terry

    From Richard Damon@21:1/5 to olcott on Sun Jun 5 20:56:55 2022
    XPost: comp.theory, comp.lang.c, comp.lang.c++

    On 6/5/22 8:27 PM, olcott wrote:
    On 6/5/2022 6:59 PM, Mike Terry wrote:
    On 05/06/2022 22:59, Jeff Barnett wrote:
    On 6/5/2022 2:07 PM, Mike Terry wrote:
    On 05/06/2022 16:16, Alan Mackenzie wrote:
    Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
    On 05/06/2022 13:14, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 6:12 AM, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 5:14 AM, Mikko wrote:
    On 2022-06-04 19:28:19 +0000, olcott said:

    A Turing machine is said to halt whenever it reaches a >>>>>>>>>>>> configuration for which δ is not defined; this is possible >>>>>>>>>>>> because
    δ is a partial function. In fact, we will assume that no >>>>>>>>>>>> transitions are defined for any final state so the Turing >>>>>>>>>>>> machine
    will halt whenever it enters a final state.  (Linz:1990:234) >>>>>
    Linz, Peter 1990. An Introduction to Formal Languages and >>>>>>>>>>>> Automata.
    Lexington/Toronto: D. C. Heath and Company.

    When translated into ordinary software engineering terms >>>>>>>>>>>> this means
    terminated normally. In a C function this means reaching the >>>>>>>>>>>> "ret"
    instruction.

    The best equivalent to "not defined" is not "ret". Instead, "not >>>>>>>>>>> defined" should include at least:
    - HLT or any other instruction that means 'halt'
    - any undefined op code
    - any return or pop instruction if the stack is empty
    - an instruction fetch from a location that is not specifiec >>>>>>>>>>> by the
         program
    That way the analogy to Linz' definition is much better.

    Mikko

    Reaching a final state is merely the Turing machine way of saying >>>>>>>>>> terminated normally. "ret" is the C way of saying the same thing. >>>>>
    Sophistry.  What would be the turing machine equivalent of an >>>>>>>>> "abnormal termination" in C?

    An aborted simulation.

    There's no such thing on a turing machine.  It either runs and
    halts,
    or it runs forever.

    Your aborted simulation is just one final state of a turing machine, >>>>>>> which has thus halted.

    A TM "aborting" a simulation is just the TM ceasing to calculate
    computation steps for some computation, and going on to calculate
    something else instead.  It does not mean:
    a)  that the TM (doing the simulation) has halted
    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    OK.  I've a feeling we're talking more about nice shades of words than >>>>> computer science here, but ....

    If the simulation is the entire turing machine, aborting it will bring >>>>> the TM to a halt state.  If that simulation is merely part of the TM, >>>>> then the word "halt" has a different meaning when applied to that
    simulation part from when applied to the entire TM.  I'm not even sure >>>>> what you mean when you say a part of a TM has halted or not halted.

    We are clearly talking at cross purposes - I never talked about
    /part/ of a TM halting, and like you, I can't work out what that
    would mean!  I used "halt" only with respect to a computation,
    meaning that the computation halts [there is an n such that
    computation step n is a TM final state].

    Reading what you say very carefully, I think that by your definition
    of simulation, the simulating TM must be a "pure" simulator that
    does nothing but simulate computation steps until the simulation
    halts, at which point the simulating TM halts (like a UTM).  I get
    that with that interpretation what you said:

    <copied from above>
    Your aborted simulation is just one final state of a turing
    machine,
    which has thus halted.

      makes sense and is correct.  I'd just say I don't think that usage >>>> of "simulation" is very useful, and is DEFINITELY not what PO is
    talking about (so it would be wrong if applied PO's posts...)

    My use of "simulation" is broader: it's simply the activity
    performed by a TM which consists of calculating computation steps of
    some given computation.  As such it's just a part of the TM logic. A
    TM's typical use of simulation might be something like "..the TM
    simulates the computation for n steps, and if the simulation halts
    during those n steps, the TM [blah blah], /otherwise/ the TM [blah
    blah blah]...". Just about every reference in the literature I can
    recall is something like that.

    So... to be 100% clear on what I said:

    <copied from above>
    A TM "aborting" a simulation is just the TM ceasing to calculate
    computation steps for some computation, and going on to calculate >>>>  >> something else instead.

    E.g. in PO's P, after P aborts its simulation of P(P), the TM either
    halts or enters an infinite loop.  (That logic is not part of the
    simulation, IMO.)

    It does *NOT* mean:
    a)  that the TM (doing the simulation) has halted

    obviously, because now P has gone on to something else...

    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    obviously - in general different exacmples of a simulated
    computation P(I) might halt or never halt, and this is unaffected by
    a simulator's decision to simulate no further computation steps.
    [The TM may have spotted some pattern in the simulated computation
    which implies P(I) never halts - that is a separate matter, but for
    sure the mere act of "aborting" the simulation doesn't imply P(I)
    never halts, or imply that it halts...

    Put yet another way, when a TM stops calculating TM steps (aka
    aborts its simulation), NOTHING HALTS: not the simulating TM, not
    the simulated computation, and NOT ANY PART OF EITHER OF THOSE.
    (Like you say, what would part of a TM halting mean?)

    I think of a TM and an input string as defining a sequence (an
    ordered list). The elements of the sequence are pairs of a TM state
    name and a string representing the "tape" contents when the state was
    entered. Note that this view has no character of animation in it and
    makes the definition of the halt predicate (H) trivial:

    H(TM,STRING) = If length of TM(STRING) is finite then TRUE else FALSE.

    Yes, that's equivalent to what I said (or at least meant).  Your
    sequence is my computation steps. Formally, these would be defined
    inductively via the rule to go from step n to step n+1.  (Not an
    animation, but the induction gives some /sense/ of step-by-step
    calculation, and a simulator will follow this, starting at step 1,
    then calculate step 2 and so on.  Still, I agree the entire sequence
    [the "computation"] exists as one timeless structure.  Too abstract
    for PO...)


    In other words when we make sure to conflate the program under test with
    the test program as a single computation then the whole idea of a halt decider becomes less coherent and

    this can be used as an excuse to pretend that you don't already know
    that H(P,P)==0 is correct and the H/P relationship matches the halting problem counter example template.

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

    int main()
    {
      Output("Input_Halts = ", H((u32)P, (u32)P));
    }

         For any program H that might determine if programs halt, a "pathological"
         program P, called with some input, can pass its own source and its input to
         H and then specifically do the opposite of what H predicts P will do. No H
         can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem



    A simulator animates the production of the sequence and that causes
    some difficulties in the same way that elaborating an infinite sum or
    sequence does in math classes. An (ultimate) value only exists if
    there is some notation of convergence or limit which typically is the
    case with examples used in a math class. There is no definition of
    convergence or limit with the sequence defined by TM(STRING); rather,
    we simply ask about the last pair if the sequence is finite.

    Sure.
    The question right now is what you would call a TM which evaluates the
    first 10 steps of a computation, and then does something else.  What
    is it doing while evaluating those 10 steps?

    tl;dr : who cares :)

    My terminology would be that it's "simulating" the computation (just
    for 10 steps) - then it stops simulating and does something else.
    Obviously I wouldn't describe it as "correctly" simulating, because
    nobody considers incorrect simulations, so the word would be redundant!

    It is required because my reviewers are making their best possible
    effort to form rebuttals and the most persistent of the fake rebuttals
    has been that the simulation is incorrect.  It is very easy to verify
    the correct x86 emulation on the basis of the x86 language.

    Except that it doesn't. By DEFINITION, a correct simulation needs show
    the same behavior of the thing it is simulating.

    Thus, since the input to H(P,P) represents the computation P(P) [at
    least if H claims to be a Halt Decider], then a correct simulation of
    that input needs to behave the same actual machine it represents.

    Since P(P) Halts if H(P,P) returns 0, then H(P,P) returning 0 can not be
    the correct answer for the behavior of P(P).


     Others have referred to that as an "incorrect simulation" because it
    stops calculating computation steps before a final state is reached.
    [Or maybe it's "incorrect" because after it aborts the simulation, H

    My point exactly.

    You might be able to claim a correct partial simulation (excpet you
    don't trace nesting right), but the partial d


    proceeds to return the wrong result?  ..which is considered part of
    the simulation?"  ...  Well, there are loads of ok ways to analyse and
    phrase what's going on I guess, as long as we're consistent.


    But nobody is going to put in all the work required to achieve a
    consensus on this

    The foundation is simple software engineering that H(P,P)==0 on the
    basis that a complete simulation of the input to H(P,P) by H would never reach the "ret" instruction of P.

    The ONLY time that H does a COMPLETE SIMULATION, is if H never aborts
    its simulation.

    H must be a definite program.

    If H IS that program that never aborts, then yes, P(P) is non-halting
    and Halts(P,P) == 0 would be correct, but H can NEVER generate that
    answer, as that behavior was derived from the assumption that H never
    aborts its simulation. Thus any argument that breaks that assumption is UNSOUND.

    If H does abort its simulation, then it never did a COMPLETE SIMULATION,
    and never will, and thus "the complete simulation by H" is a
    non-existant entity, it is the liars paradox. You can't base a proof on
    the properties of something that doesn't actually exist.

    Any claims that these two possibilities for H can exist at the same time
    is just an admission that H is not the required computation, as it
    doesn;t always act the same way to the same input.

    If you want to claim that it is possible for a computation to act
    differently for different instances with the exact same input, then you
    really need to PROVE that claim. If you can, that alone would make you
    famous, but it seems you don't even know enough about the field to
    understand the need to prove that claim, so I really doubt you have a
    way to prove it. (Again, the proof that it always acts the same is so foundationally simple, I can't imagine you having a way to actually
    disprove it.



    here, especially with PO who couldn't understand the distinctions.  ]


    Mike.



    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Mike Terry on Sun Jun 5 19:27:39 2022
    XPost: comp.theory, comp.lang.c, comp.lang.c++

    On 6/5/2022 6:59 PM, Mike Terry wrote:
    On 05/06/2022 22:59, Jeff Barnett wrote:
    On 6/5/2022 2:07 PM, Mike Terry wrote:
    On 05/06/2022 16:16, Alan Mackenzie wrote:
    Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
    On 05/06/2022 13:14, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 6:12 AM, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 5:14 AM, Mikko wrote:
    On 2022-06-04 19:28:19 +0000, olcott said:

    A Turing machine is said to halt whenever it reaches a
    configuration for which δ is not defined; this is possible >>>>>>>>>>> because
    δ is a partial function. In fact, we will assume that no >>>>>>>>>>> transitions are defined for any final state so the Turing >>>>>>>>>>> machine
    will halt whenever it enters a final state.  (Linz:1990:234)

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

    When translated into ordinary software engineering terms this >>>>>>>>>>> means
    terminated normally. In a C function this means reaching the >>>>>>>>>>> "ret"
    instruction.

    The best equivalent to "not defined" is not "ret". Instead, "not >>>>>>>>>> defined" should include at least:
    - HLT or any other instruction that means 'halt'
    - any undefined op code
    - any return or pop instruction if the stack is empty
    - an instruction fetch from a location that is not specifiec >>>>>>>>>> by the
         program
    That way the analogy to Linz' definition is much better.

    Mikko

    Reaching a final state is merely the Turing machine way of saying >>>>>>>>> terminated normally. "ret" is the C way of saying the same thing. >>>>
    Sophistry.  What would be the turing machine equivalent of an >>>>>>>> "abnormal termination" in C?

    An aborted simulation.

    There's no such thing on a turing machine.  It either runs and halts, >>>>>> or it runs forever.

    Your aborted simulation is just one final state of a turing machine, >>>>>> which has thus halted.

    A TM "aborting" a simulation is just the TM ceasing to calculate
    computation steps for some computation, and going on to calculate
    something else instead.  It does not mean:
    a)  that the TM (doing the simulation) has halted
    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    OK.  I've a feeling we're talking more about nice shades of words than >>>> computer science here, but ....

    If the simulation is the entire turing machine, aborting it will bring >>>> the TM to a halt state.  If that simulation is merely part of the TM, >>>> then the word "halt" has a different meaning when applied to that
    simulation part from when applied to the entire TM.  I'm not even sure >>>> what you mean when you say a part of a TM has halted or not halted.

    We are clearly talking at cross purposes - I never talked about
    /part/ of a TM halting, and like you, I can't work out what that
    would mean!  I used "halt" only with respect to a computation,
    meaning that the computation halts [there is an n such that
    computation step n is a TM final state].

    Reading what you say very carefully, I think that by your definition
    of simulation, the simulating TM must be a "pure" simulator that does
    nothing but simulate computation steps until the simulation halts, at
    which point the simulating TM halts (like a UTM).  I get that with
    that interpretation what you said:

    <copied from above>
    Your aborted simulation is just one final state of a turing
    machine,
    which has thus halted.

      makes sense and is correct.  I'd just say I don't think that usage
    of "simulation" is very useful, and is DEFINITELY not what PO is
    talking about (so it would be wrong if applied PO's posts...)

    My use of "simulation" is broader: it's simply the activity performed
    by a TM which consists of calculating computation steps of some given
    computation.  As such it's just a part of the TM logic. A TM's
    typical use of simulation might be something like "..the TM simulates
    the computation for n steps, and if the simulation halts during those
    n steps, the TM [blah blah], /otherwise/ the TM [blah blah blah]...".
    Just about every reference in the literature I can recall is
    something like that.

    So... to be 100% clear on what I said:

    <copied from above>
    A TM "aborting" a simulation is just the TM ceasing to calculate
    computation steps for some computation, and going on to calculate
    something else instead.

    E.g. in PO's P, after P aborts its simulation of P(P), the TM either
    halts or enters an infinite loop.  (That logic is not part of the
    simulation, IMO.)

    It does *NOT* mean:
    a)  that the TM (doing the simulation) has halted

    obviously, because now P has gone on to something else...

    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    obviously - in general different exacmples of a simulated computation
    P(I) might halt or never halt, and this is unaffected by a
    simulator's decision to simulate no further computation steps. [The
    TM may have spotted some pattern in the simulated computation which
    implies P(I) never halts - that is a separate matter, but for sure
    the mere act of "aborting" the simulation doesn't imply P(I) never
    halts, or imply that it halts...

    Put yet another way, when a TM stops calculating TM steps (aka aborts
    its simulation), NOTHING HALTS: not the simulating TM, not the
    simulated computation, and NOT ANY PART OF EITHER OF THOSE. (Like you
    say, what would part of a TM halting mean?)

    I think of a TM and an input string as defining a sequence (an ordered
    list). The elements of the sequence are pairs of a TM state name and a
    string representing the "tape" contents when the state was entered.
    Note that this view has no character of animation in it and makes the
    definition of the halt predicate (H) trivial:

    H(TM,STRING) = If length of TM(STRING) is finite then TRUE else FALSE.

    Yes, that's equivalent to what I said (or at least meant).  Your
    sequence is my computation steps. Formally, these would be defined inductively via the rule to go from step n to step n+1.  (Not an
    animation, but the induction gives some /sense/ of step-by-step
    calculation, and a simulator will follow this, starting at step 1, then calculate step 2 and so on.  Still, I agree the entire sequence [the "computation"] exists as one timeless structure.  Too abstract for PO...)


    In other words when we make sure to conflate the program under test with
    the test program as a single computation then the whole idea of a halt
    decider becomes less coherent and

    this can be used as an excuse to pretend that you don't already know
    that H(P,P)==0 is correct and the H/P relationship matches the halting
    problem counter example template.

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

    int main()
    {
    Output("Input_Halts = ", H((u32)P, (u32)P));
    }

    For any program H that might determine if programs halt, a
    "pathological"
    program P, called with some input, can pass its own source and its
    input to
    H and then specifically do the opposite of what H predicts P will
    do. No H
    can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem



    A simulator animates the production of the sequence and that causes
    some difficulties in the same way that elaborating an infinite sum or
    sequence does in math classes. An (ultimate) value only exists if
    there is some notation of convergence or limit which typically is the
    case with examples used in a math class. There is no definition of
    convergence or limit with the sequence defined by TM(STRING); rather,
    we simply ask about the last pair if the sequence is finite.

    Sure.
    The question right now is what you would call a TM which evaluates the
    first 10 steps of a computation, and then does something else.  What is
    it doing while evaluating those 10 steps?

    tl;dr : who cares :)

    My terminology would be that it's "simulating" the computation (just for
    10 steps) - then it stops simulating and does something else.  Obviously
    I wouldn't describe it as "correctly" simulating, because nobody
    considers incorrect simulations, so the word would be redundant!

    It is required because my reviewers are making their best possible
    effort to form rebuttals and the most persistent of the fake rebuttals
    has been that the simulation is incorrect. It is very easy to verify
    the correct x86 emulation on the basis of the x86 language.

    Others
    have referred to that as an "incorrect simulation" because it stops calculating computation steps before a final state is reached.  [Or
    maybe it's "incorrect" because after it aborts the simulation, H

    My point exactly.

    proceeds to return the wrong result?  ..which is considered part of the simulation?"  ...  Well, there are loads of ok ways to analyse and
    phrase what's going on I guess, as long as we're consistent.


    But nobody
    is going to put in all the work required to achieve a consensus on this

    The foundation is simple software engineering that H(P,P)==0 on the
    basis that a complete simulation of the input to H(P,P) by H would never
    reach the "ret" instruction of P.

    here, especially with PO who couldn't understand the distinctions.  ]


    Mike.


    --
    Copyright 2022 Pete Olcott

    "Talent hits a target no one else can hit;
    Genius hits a target no one else can see."
    Arthur Schopenhauer

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mr Flibble@21:1/5 to olcott on Mon Jun 6 17:49:52 2022
    XPost: comp.theory, comp.lang.c, comp.lang.c++

    On Sun, 5 Jun 2022 19:27:39 -0500
    olcott <NoOne@NoWhere.com> wrote:

    On 6/5/2022 6:59 PM, Mike Terry wrote:
    On 05/06/2022 22:59, Jeff Barnett wrote:
    On 6/5/2022 2:07 PM, Mike Terry wrote:
    On 05/06/2022 16:16, Alan Mackenzie wrote:
    Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
    On 05/06/2022 13:14, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 6:12 AM, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 5:14 AM, Mikko wrote:
    On 2022-06-04 19:28:19 +0000, olcott said:

    A Turing machine is said to halt whenever it reaches a >>>>>>>>>>> configuration for which δ is not defined; this is
    possible because
    δ is a partial function. In fact, we will assume that no >>>>>>>>>>> transitions are defined for any final state so the Turing >>>>>>>>>>> machine
    will halt whenever it enters a final state.
    (Linz:1990:234)

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

    When translated into ordinary software engineering terms >>>>>>>>>>> this means
    terminated normally. In a C function this means reaching >>>>>>>>>>> the "ret"
    instruction.

    The best equivalent to "not defined" is not "ret".
    Instead, "not defined" should include at least:
    - HLT or any other instruction that means 'halt'
    - any undefined op code
    - any return or pop instruction if the stack is empty
    - an instruction fetch from a location that is not
    specifiec by the
         program
    That way the analogy to Linz' definition is much better.

    Mikko

    Reaching a final state is merely the Turing machine way of >>>>>>>>> saying terminated normally. "ret" is the C way of saying
    the same thing.

    Sophistry.  What would be the turing machine equivalent of an >>>>>>>> "abnormal termination" in C?

    An aborted simulation.

    There's no such thing on a turing machine.  It either runs and
    halts, or it runs forever.

    Your aborted simulation is just one final state of a turing
    machine, which has thus halted.

    A TM "aborting" a simulation is just the TM ceasing to calculate
    computation steps for some computation, and going on to
    calculate something else instead.  It does not mean:
    a)  that the TM (doing the simulation) has halted
    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    OK.  I've a feeling we're talking more about nice shades of
    words than computer science here, but ....

    If the simulation is the entire turing machine, aborting it will
    bring the TM to a halt state.  If that simulation is merely part
    of the TM, then the word "halt" has a different meaning when
    applied to that simulation part from when applied to the entire
    TM.  I'm not even sure what you mean when you say a part of a TM
    has halted or not halted.

    We are clearly talking at cross purposes - I never talked about
    /part/ of a TM halting, and like you, I can't work out what that
    would mean!  I used "halt" only with respect to a computation,
    meaning that the computation halts [there is an n such that
    computation step n is a TM final state].

    Reading what you say very carefully, I think that by your
    definition of simulation, the simulating TM must be a "pure"
    simulator that does nothing but simulate computation steps until
    the simulation halts, at which point the simulating TM halts
    (like a UTM).  I get that with that interpretation what you said:

    <copied from above>
    Your aborted simulation is just one final state of a turing
    machine,
    which has thus halted.

      makes sense and is correct.  I'd just say I don't think that
    usage of "simulation" is very useful, and is DEFINITELY not what
    PO is talking about (so it would be wrong if applied PO's
    posts...)

    My use of "simulation" is broader: it's simply the activity
    performed by a TM which consists of calculating computation steps
    of some given computation.  As such it's just a part of the TM
    logic. A TM's typical use of simulation might be something like
    "..the TM simulates the computation for n steps, and if the
    simulation halts during those n steps, the TM [blah blah],
    /otherwise/ the TM [blah blah blah]...". Just about every
    reference in the literature I can recall is something like that.

    So... to be 100% clear on what I said:

    <copied from above>
    A TM "aborting" a simulation is just the TM ceasing to
    calculate >> computation steps for some computation, and going on
    to calculate >> something else instead.

    E.g. in PO's P, after P aborts its simulation of P(P), the TM
    either halts or enters an infinite loop.  (That logic is not part
    of the simulation, IMO.)

    It does *NOT* mean:
    a)  that the TM (doing the simulation) has halted

    obviously, because now P has gone on to something else...

    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    obviously - in general different exacmples of a simulated
    computation P(I) might halt or never halt, and this is unaffected
    by a simulator's decision to simulate no further computation
    steps. [The TM may have spotted some pattern in the simulated
    computation which implies P(I) never halts - that is a separate
    matter, but for sure the mere act of "aborting" the simulation
    doesn't imply P(I) never halts, or imply that it halts...

    Put yet another way, when a TM stops calculating TM steps (aka
    aborts its simulation), NOTHING HALTS: not the simulating TM, not
    the simulated computation, and NOT ANY PART OF EITHER OF THOSE.
    (Like you say, what would part of a TM halting mean?)

    I think of a TM and an input string as defining a sequence (an
    ordered list). The elements of the sequence are pairs of a TM
    state name and a string representing the "tape" contents when the
    state was entered. Note that this view has no character of
    animation in it and makes the definition of the halt predicate (H)
    trivial:

    H(TM,STRING) = If length of TM(STRING) is finite then TRUE else
    FALSE.

    Yes, that's equivalent to what I said (or at least meant).  Your
    sequence is my computation steps. Formally, these would be defined inductively via the rule to go from step n to step n+1.  (Not an animation, but the induction gives some /sense/ of step-by-step calculation, and a simulator will follow this, starting at step 1,
    then calculate step 2 and so on.  Still, I agree the entire
    sequence [the "computation"] exists as one timeless structure.  Too abstract for PO...)

    In other words when we make sure to conflate the program under test
    with the test program as a single computation then the whole idea of
    a halt decider becomes less coherent and

    I asserted that it is erroneous to conflate the decider with that which
    is being decided several months ago. No such conflation occurs in the
    HP proofs you are attempting to refute; it is your conflation which is erroneous.

    /Flibble

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Mr Flibble on Mon Jun 6 11:59:02 2022
    XPost: comp.theory, sci.logic, sci.math

    On 6/6/2022 11:49 AM, Mr Flibble wrote:
    On Sun, 5 Jun 2022 19:27:39 -0500
    olcott <NoOne@NoWhere.com> wrote:

    On 6/5/2022 6:59 PM, Mike Terry wrote:
    On 05/06/2022 22:59, Jeff Barnett wrote:
    On 6/5/2022 2:07 PM, Mike Terry wrote:
    On 05/06/2022 16:16, Alan Mackenzie wrote:
    Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
    On 05/06/2022 13:14, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 6:12 AM, Alan Mackenzie wrote:
    olcott <NoOne@nowhere.com> wrote:
    On 6/5/2022 5:14 AM, Mikko wrote:
    On 2022-06-04 19:28:19 +0000, olcott said:

    A Turing machine is said to halt whenever it reaches a >>>>>>>>>>>>> configuration for which δ is not defined; this is
    possible because
    δ is a partial function. In fact, we will assume that no >>>>>>>>>>>>> transitions are defined for any final state so the Turing >>>>>>>>>>>>> machine
    will halt whenever it enters a final state.
    (Linz:1990:234)

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

    When translated into ordinary software engineering terms >>>>>>>>>>>>> this means
    terminated normally. In a C function this means reaching >>>>>>>>>>>>> the "ret"
    instruction.

    The best equivalent to "not defined" is not "ret".
    Instead, "not defined" should include at least:
    - HLT or any other instruction that means 'halt'
    - any undefined op code
    - any return or pop instruction if the stack is empty
    - an instruction fetch from a location that is not
    specifiec by the
         program
    That way the analogy to Linz' definition is much better.

    Mikko

    Reaching a final state is merely the Turing machine way of >>>>>>>>>>> saying terminated normally. "ret" is the C way of saying >>>>>>>>>>> the same thing.

    Sophistry.  What would be the turing machine equivalent of an >>>>>>>>>> "abnormal termination" in C?

    An aborted simulation.

    There's no such thing on a turing machine.  It either runs and >>>>>>>> halts, or it runs forever.

    Your aborted simulation is just one final state of a turing
    machine, which has thus halted.

    A TM "aborting" a simulation is just the TM ceasing to calculate >>>>>>> computation steps for some computation, and going on to
    calculate something else instead.  It does not mean:
    a)  that the TM (doing the simulation) has halted
    b)  that the simulated computation halts
    c)  that the simulated computation never halts

    OK.  I've a feeling we're talking more about nice shades of
    words than computer science here, but ....

    If the simulation is the entire turing machine, aborting it will
    bring the TM to a halt state.  If that simulation is merely part
    of the TM, then the word "halt" has a different meaning when
    applied to that simulation part from when applied to the entire
    TM.  I'm not even sure what you mean when you say a part of a TM
    has halted or not halted.

    We are clearly talking at cross purposes - I never talked about
    /part/ of a TM halting, and like you, I can't work out what that
    would mean!  I used "halt" only with respect to a computation,
    meaning that the computation halts [there is an n such that
    computation step n is a TM final state].

    Reading what you say very carefully, I think that by your
    definition of simulation, the simulating TM must be a "pure"
    simulator that does nothing but simulate computation steps until
    the simulation halts, at which point the simulating TM halts
    (like a UTM).  I get that with that interpretation what you said:

    <copied from above>
    ; Your aborted simulation is just one final state of a turing
    machine,
    ; which has thus halted.

      makes sense and is correct.  I'd just say I don't think that
    usage of "simulation" is very useful, and is DEFINITELY not what
    PO is talking about (so it would be wrong if applied PO's
    posts...)

    My use of "simulation" is broader: it's simply the activity
    performed by a TM which consists of calculating computation steps
    of some given computation.  As such it's just a part of the TM
    logic. A TM's typical use of simulation might be something like
    "..the TM simulates the computation for n steps, and if the
    simulation halts during those n steps, the TM [blah blah],
    /otherwise/ the TM [blah blah blah]...". Just about every
    reference in the literature I can recall is something like that.

    So... to be 100% clear on what I said:

    <copied from above>
    ; A TM "aborting" a simulation is just the TM ceasing to
    calculate >> computation steps for some computation, and going on
    to calculate >> something else instead.

    E.g. in PO's P, after P aborts its simulation of P(P), the TM
    either halts or enters an infinite loop.  (That logic is not part
    of the simulation, IMO.)

    ; It does *NOT* mean:
    ; a)  that the TM (doing the simulation) has halted

    obviously, because now P has gone on to something else...

    ; b)  that the simulated computation halts
    ; c)  that the simulated computation never halts

    obviously - in general different exacmples of a simulated
    computation P(I) might halt or never halt, and this is unaffected
    by a simulator's decision to simulate no further computation
    steps. [The TM may have spotted some pattern in the simulated
    computation which implies P(I) never halts - that is a separate
    matter, but for sure the mere act of "aborting" the simulation
    doesn't imply P(I) never halts, or imply that it halts...

    Put yet another way, when a TM stops calculating TM steps (aka
    aborts its simulation), NOTHING HALTS: not the simulating TM, not
    the simulated computation, and NOT ANY PART OF EITHER OF THOSE.
    (Like you say, what would part of a TM halting mean?)

    I think of a TM and an input string as defining a sequence (an
    ordered list). The elements of the sequence are pairs of a TM
    state name and a string representing the "tape" contents when the
    state was entered. Note that this view has no character of
    animation in it and makes the definition of the halt predicate (H)
    trivial:

    H(TM,STRING) = If length of TM(STRING) is finite then TRUE else
    FALSE.

    Yes, that's equivalent to what I said (or at least meant).  Your
    sequence is my computation steps. Formally, these would be defined
    inductively via the rule to go from step n to step n+1.  (Not an
    animation, but the induction gives some /sense/ of step-by-step
    calculation, and a simulator will follow this, starting at step 1,
    then calculate step 2 and so on.  Still, I agree the entire
    sequence [the "computation"] exists as one timeless structure.  Too
    abstract for PO...)

    In other words when we make sure to conflate the program under test
    with the test program as a single computation then the whole idea of
    a halt decider becomes less coherent and

    I asserted that it is erroneous to conflate the decider with that which
    is being decided several months ago. No such conflation occurs in the
    HP proofs you are attempting to refute; it is your conflation which is erroneous.

    /Flibble


    Did you notice that I was replying to Mike Terry?

    --
    Copyright 2022 Pete Olcott

    "Talent hits a target no one else can hit;
    Genius hits a target no one else can see."
    Arthur Schopenhauer

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