• The key mistake of the Peter Linz HP proof

    From olcott@21:1/5 to All on Fri Sep 3 19:18:05 2021
    XPost: comp.theory, comp.software-eng, sci.math

    In computability theory, the halting problem is the
    problem of determining, from a description of an arbitrary
    computer program and an input,

    whether the simulation of this program must be aborted to
    prevent it from running forever.

    The above criteria is valid on the basis of the known equivalence
    between the direct execution of a computation and its simulation
    by a UTM. The same criteria universally works on all inputs allowing
    their halting status to be correctly decided.

    The Peter Linz H is defined to be a simulating halt decider that applies
    the above criteria and the halt decider at Ĥ.qx is an exact copy of H.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    The mistake of the Linz proof is forming a conclusion
    based on Ĥ applied to its own Turing machine description ⟨Ĥ⟩.

    This is only answering the question:
    Can changes be made to an otherwise correct halt decider
    such that this halt decider is no longer correct?

    The required question is:
    Does the original H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decide the halt status
    of its input?

    Yes the original H does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩

    This is proved in section V3 of my paper by the analogous example of:
    int main() { H1(P,P); } // analogous to H applied to ⟨Ĥ⟩ ⟨Ĥ⟩

    https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

    The full Linz Proof: https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

    --
    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 Richard Damon on Sat Sep 4 09:06:34 2021
    XPost: comp.theory, comp.software-eng, sci.logic

    On 9/4/2021 5:50 AM, Richard Damon wrote:
    On 9/3/21 10:13 PM, olcott wrote:
    On 9/3/2021 8:53 PM, Richard Damon wrote:
    On 9/3/21 9:18 PM, olcott wrote:
    On 9/3/2021 8:05 PM, Richard Damon wrote:
    On 9/3/21 8:18 PM, olcott wrote:
         In computability theory, the halting problem is the
         problem of determining, from a description of an arbitrary >>>>>>      computer program and an input,

         whether the simulation of this program must be aborted to >>>>>>      prevent it from running forever.

    The above criteria is valid on the basis of the known equivalence
    between the direct execution of a computation and its simulation
    by a UTM. The same criteria universally works on all inputs allowing >>>>>> their halting status to be correctly decided.

    The Peter Linz H is defined to be a simulating halt decider that
    applies
    the above criteria and the halt decider at Ĥ.qx is an exact copy of H. >>>>>>
    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    The mistake of the Linz proof is forming a conclusion
    based on Ĥ applied to its own Turing machine description ⟨Ĥ⟩. >>>>>>
    This is only answering the question:
    Can changes be made to an otherwise correct halt decider
    such that this halt decider is no longer correct?

    The required question is:
    Does the original H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decide the halt
    status
    of its input?

    Yes the original H does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩

    This is proved in section V3 of my paper by the analogous example of: >>>>>> int main() { H1(P,P); }  // analogous to H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ >>>>>>
    https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation




    The full Linz Proof:
    https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf


    So, do you claim H1 is the SAME computation as H, and thus neither is >>>>> actually a computation as the same computation can't give two different >>>>> answers to the same input.


    I claim that H1 has identical machine code as H.
    Their execution order makes them distinctly different computations.

    H1 can see that H(P,P) aborts the simulation of its input.
    H(P,P) cannot see anything that aborts the simulation of its input.

    This execution sequence order makes them distinctly different
    computations.

    This is exactly the same as the when the original Linz H is applied to >>>> ⟨Ĥ⟩ ⟨Ĥ⟩.

    IF H1 is a different computation than H, then the fact that it can get
    the answer right doesn't matter, as it wasn't the computation that H^
    was built on.


    The Linz Ĥ is only required to have an exact copy of the Linz H at Ĥ.qx. >> It turns out that using my simulating halt decider criteria H would
    correctly report that its input ⟨Ĥ⟩ ⟨Ĥ⟩ halts.

    Not quite, you are missing the meaning of words here. H was supposed to
    be a Turing Machine, an exact copy of a Turing Machine will behave identically to the original. This is a fundamental property of being a Computation, if you make an exact copy of the algorithm, you will get
    the identical behavior.
    I have empirically proved that this is merely a false assumption.
    int main() { H1(P,P); } sees a different execution trace than H(P,P).

    In the first case we have a halt decider that sees another halt decider
    abort the simulation of its input.

    In the second case we have a halt decider that does not see another halt decider abort the simulation of its input.

    The execution order of with H1 before H derives a different execution
    trace for H1 than for H.

    H1 is an identical copy of H and has different behavior than H because
    its execution trace input is different than H.

    --
    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 Richard Damon on Sat Sep 4 10:16:27 2021
    XPost: comp.theory, comp.theory, sci.logic

    On 9/4/2021 9:18 AM, Richard Damon wrote:
    On 9/4/21 10:06 AM, olcott wrote:
    On 9/4/2021 5:50 AM, Richard Damon wrote:
    On 9/3/21 10:13 PM, olcott wrote:
    On 9/3/2021 8:53 PM, Richard Damon wrote:
    On 9/3/21 9:18 PM, olcott wrote:
    On 9/3/2021 8:05 PM, Richard Damon wrote:
    On 9/3/21 8:18 PM, olcott wrote:
          In computability theory, the halting problem is the >>>>>>>>       problem of determining, from a description of an arbitrary >>>>>>>>       computer program and an input,

          whether the simulation of this program must be aborted to >>>>>>>>       prevent it from running forever.

    The above criteria is valid on the basis of the known equivalence >>>>>>>> between the direct execution of a computation and its simulation >>>>>>>> by a UTM. The same criteria universally works on all inputs allowing >>>>>>>> their halting status to be correctly decided.

    The Peter Linz H is defined to be a simulating halt decider that >>>>>>>> applies
    the above criteria and the halt decider at Ĥ.qx is an exact copy >>>>>>>> of H.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    The mistake of the Linz proof is forming a conclusion
    based on Ĥ applied to its own Turing machine description ⟨Ĥ⟩. >>>>>>>>
    This is only answering the question:
    Can changes be made to an otherwise correct halt decider
    such that this halt decider is no longer correct?

    The required question is:
    Does the original H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decide the halt
    status
    of its input?

    Yes the original H does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩

    This is proved in section V3 of my paper by the analogous example >>>>>>>> of:
    int main() { H1(P,P); }  // analogous to H applied to ⟨Ĥ⟩ ⟨Ĥ⟩

    https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation





    The full Linz Proof:
    https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf


    So, do you claim H1 is the SAME computation as H, and thus neither is >>>>>>> actually a computation as the same computation can't give two
    different
    answers to the same input.


    I claim that H1 has identical machine code as H.
    Their execution order makes them distinctly different computations. >>>>>>
    H1 can see that H(P,P) aborts the simulation of its input.
    H(P,P) cannot see anything that aborts the simulation of its input. >>>>>>
    This execution sequence order makes them distinctly different
    computations.

    This is exactly the same as the when the original Linz H is applied to >>>>>> ⟨Ĥ⟩ ⟨Ĥ⟩.

    IF H1 is a different computation than H, then the fact that it can get >>>>> the answer right doesn't matter, as it wasn't the computation that H^ >>>>> was built on.


    The Linz Ĥ is only required to have an exact copy of the Linz H at Ĥ.qx. >>>> It turns out that using my simulating halt decider criteria H would
    correctly report that its input ⟨Ĥ⟩ ⟨Ĥ⟩ halts.

    Not quite, you are missing the meaning of words here. H was supposed to
    be a Turing Machine, an exact copy of a Turing Machine will behave
    identically to the original. This is a fundamental property of being a
    Computation, if you make an exact copy of the algorithm, you will get
    the identical behavior.
    I have empirically proved that this is merely a false assumption.
    int main() { H1(P,P); } sees a different execution trace than H(P,P).

    In the first case we have a halt decider that sees another halt decider
    abort the simulation of its input.

    In the second case we have a halt decider that does not see another halt
    decider abort the simulation of its input.

    The execution order of with H1 before H derives a different execution
    trace for H1 than for H.

    H1 is an identical copy of H and has different behavior than H because
    its execution trace input is different than H.


    Since Execution Trace is NOT defined as an input to that Computation
    (the only inputs are the representation of the machine and its input),
    the dependency of the result on that just proves that H and H1 are not properly Computation, and thus not eligable to be a Decider.

    PERIOD. DEFINITION.

    The input to the halt deciders is their different execution trace thus
    the halt deciders are a pure function of their input.

    H is NOT the Computational Equivalent of the Turing Machine it is
    claimed to be, as that machine would be Computation (as Turing Machines,
    but structure HAVE to be), so you argument fails at line 1 when you make
    that claim.

    You clearly do not understand the meaning of Computation as used in the
    field you are trying to muddle in.



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