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

  • What is a computation? (over Richard's head)

    From olcott@21:1/5 to Richard Damon on Thu Apr 15 10:26:44 2021
    XPost: comp.theory

    On 4/15/2021 6:19 AM, Richard Damon wrote:
    On 4/14/21 9:53 PM, olcott wrote:
    On 4/14/2021 8:36 PM, Richard Damon wrote:
    On 4/14/21 9:14 PM, olcott wrote:
    On 4/14/2021 7:55 PM, Richard Damon wrote:
    On 4/14/21 11:09 AM, olcott wrote:
    On 4/12/2021 10:49 PM, Richard Damon wrote:
    On 4/12/21 11:37 PM, olcott wrote:
    On 4/12/2021 10:17 PM, Richard Damon wrote:
    On 4/12/21 10:46 PM, olcott wrote:
    On 4/12/2021 12:04 PM, Richard Damon wrote:

    You have that rule WRONG. IF H is infinitely recursive,

    You can't even pay attention to the words that I am saying. >>>>>>>>>>
    H is not frigging infinitely recursive H_Hat is calling H in >>>>>>>>>> infinite
    recursion. It is the error of H_Hat, it is not the error of H. >>>>>>>>>>

    How is one infinitely recursive and not the other?

    The execution path that you claim to be infinite recursion would >>>>>>>>> be:

    H_Hat --> Halts --> H_Hat --> Halts --> H_Hat --> Halts

    Wrong.

    Halts --> H_Hat --> Halts --> H_Hat --> Halts --> H_Hat is aborted. >>>>>>>>

    SO Halts as a top level gets aborted and Halts doesn't get a
    chance to
    answer?

    The key it that this is a MUTUAL recursion, either both are
    infinite or
    neither is. You can't say one is but the other isn't.

    The only alternative is to admit that Halts isn't a computation, >>>>>>> so it
    can't be the needed decider.


    When X calls Y in infinite recursion and Y is being simulated by X >>>>>> then
    X can stop simulating Y.


    And thus, if Y calls X to simumulate Y, then X can stop the simulation >>>>> of Y and return the answer to the calling Y.


    If I was going to over-ride the infinite recursion I might as well
    change H_Hat to get rid of its infinite loop:

    Halts has to decide what it is going to do, and always do the same thing >>> under the same conditions (as far as its formal inputs are concerned).

    Yes I agree with this.

    If it isn't then it isn't a Computation and can't be a Turing Machine
    Equivalent as claimed.


    That makes sense to me.

    Either it ALWAYS aborts the infinite recursion at the point that it
    makes the decision and return that same answer to what ever caller made
    the request,

    The call to Halts from main is not infinitely recursive and it the first
    call. The call to Halts from H_Hat is not an actual call it is part of
    the simulation of H_Hat which the actual call to Halts from main aborts.

    A Call to Halts is a call to Halts. When H_Hat is the top level function
    call in main, and then that H_Hat calls Halts, that call MUST be
    identical to Halts to when main called Halts directly, Halts has no way
    to tell the difference.



    Yes this is correct.

    Yes, inside the simulation, Halts can see within the simulation a call
    tree of H_Hat -> Halts -> H_Hat

    Great.

    and decide (incorrectly) that we have an
    infinite recursion and abort the simulation and return the answer, to
    either main or the top level call in H_Hat.

    Halts is correctly answering the question:
    Does your input terminate whenif its simulation is not stopped?


    or it NEVER makes that decision and never returns (and thus
    shown not to be a decider).

    Remember, It is an ALGORITHM, it has no volition and must always act the >>> same way. Maybe your problem is you think of Halts as an extension of
    your ego, like it can make volitional decisions. It is a Computation, an >>> Algorithm, a fixed process.

    repr
    Self Modifying Turing Machine (SMTM) Solution to the Halting Problem
    (concrete example) August 2016

    https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example


    Yes, I saw that, can you show me an example of a Turing Machine that
    changes its own State Machine.


    I have already shown how the DFA can changes its own state table in the
    paper. It is easy to make a self-modifying TM by merely having a UTM
    that simulates the Turing machine description of the self-modifying TM
    that writes to the description of its own state transition table.

    No, you showed how something using the DFA could change it, not how the
    DFA could change itself. In the same manner, a Turing Machine has no 'instructions' at its command to change the actual Turing State
    Transition Table. Yes, you could design a Turing Machine that was more
    of an interpreter, that had instructions on the tape and it could edit
    the tape and change the path the interpreter runs in, but that hasn't actually modified the actual Turing Machine.


    And such a self-modifying Turing machine (SMTM) could simply erase the
    infinite loop in its input and then report that its input halts.

    In this same way Halts() can ignore the fact that no function ever
    returns any value to a function that invokes it in infinite recursion
    and Halts can return "Happy Birthday to you" to H_Hat, also ignoring the
    other fact that its return value must be Boolean.

    Maybe your issue here is that you are so thinking of conventional
    processors that you are forgetting that Turing Machines have a VERY
    distinct division between the 'Algorithm' (The State Transition Table)
    and the 'Data' (The Tape), and miss the distinction.

    No I merely extended the capabilies of a TM within the conventional
    defintion of a TM. If a TM can write to its tape then a TM can write to
    its tape that contains its own TM description. Also the TM that writes
    to the tape that contains its own TM description could be simulated by
    another UTM such that the simulated TM is literally changing itself.

    Note, as described
    above, Turing Maachines are able to emmulate the effects of Self
    Modifying code, but can not themselves actually modify their own code.


    If the process that is modifying the tape locations of its own TM
    description is the simutation of this very same TM description (not a
    copy) then the TM is literally modifying itself.

    Such a process can correctly decide H_Hat because it can change itself
    so that it nor longer functions the same way as the instance of itself
    that is embedded within H_Hat.

    A Self-Modifying-Turing-Machine (SMTM) is defined as a Universal Turing
    Machine (UTM) that can dynamically modify its own TM description such
    that this SMTM can become any element of the set of Turing Machines.

    (1) Every TM / input pair either halts or fails to halt.
    (2) There exists a TM halt decider for every TM / input pair.
    (3) A SMTM can become any element of the set of TMs.
    (4) Therefore a SMTM can become a halt decider for any TM / input pair.

    Self Modifying Turing Machine (SMTM) Solution to the Halting Problem
    (concrete example)
    August 2016 PL Olcott

    https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example



    As I said below, can you show me how you would even attempt to encode an actual change to the STT for a Turing Machine?



    Can you show me how you write that Tuple?



    Not only CAN, but if X want to be a Computation, if X does it when not >>>>> called by Y, it HAS to do it when called by Y.

    Thus Halts MUST answer H_Hat.









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