Results 1 to 3 of 3

Math Help - Turing machines with a single tape.

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    Turing machines with a single tape.

    In this question, we consider Turing machines with a single tape. suppose we modify the machine to be a Splicing Turing machine STM. when a STM cuts a square out of the tape, it cuts the square where the head is currently located. After the cut, the head is located just to the right of the place where the square was cut out. For example, suppose the tape contents are abcde and the head is located at the d. If the STM inserts one square, then moves left two squares and cuts out one square, the resulting tape contents would be acd_e (where _ indicates a blank) and the head would be at the c.

    a) briefly describe hoe every STM can be simulated using an ordinary Turing Machine.

    b) Suppose you had a STM algorithm that took at most T(n) steps on all inputs of length n. Inserting a square into the tape or cutting a square out of the tape counts as a single step of the STM. Give a good upper bound on the number of steps an ordinary Turing machine would take when simulating the STM using the simulation you gave in part (a). If you like, you may use big-O notation to state your bound; you do not have to worry about constant factors. Explain Your answer please.
    Last edited by mr fantastic; November 14th 2010 at 05:08 PM. Reason: Re-titled.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765
    To simulate insertion of the new square, copy the portion of the tape that is right of the head one square to the right. Similarly, to simulate cutting of a square, copy the right portion one square to the left. This takes O(n) steps where n is the tape length.

    If the initial tape length is n and the machine makes T(n) steps, the maximal tape length is n + T(n). Thus, each of the T(n) steps of an STM can be simulated by O(n + T(n)) steps of a regular TM. To get the final big-O estimate, it may be convenient to assume that T(n) is non-decreasing and to consider two cases: n is O(T(n)) and T(n) is O(n). (Though this is not necessary.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    Thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. flaws in a tape
    Posted in the Statistics Forum
    Replies: 6
    Last Post: July 7th 2011, 09:43 AM
  3. Turing machines and decidability.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 29th 2010, 12:38 PM
  4. Single equation, single unknown. How to solve?
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: March 14th 2010, 12:37 PM
  5. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 19th 2007, 03:39 PM

Search Tags


/mathhelpforum @mathhelpforum