Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Very basic turing machines problem

  1. #1
    Junior Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    73
    Thanks
    2

    Very basic turing machines problem

    We have Turing machine M with one work tape, which is it's output. The tape heads of input and work tape can move only left and right (basic definition, there is no staying at the current position movement). And we want to execute simple algorithm. We want to duplicate each symbol on the input tape twice and write it to the output tape. So if the input tape reads >ABCDE# in respective alphabet, we want to produce >AABBCCDDEE# on the output tape. How do we do that?

    Obviously wrong way to do it: Simulate no movement of the work tape with a pair of forward - back movements.
    What will happen? We will read the current symbol on the input tape and write it to the output tape. Then we have to move both tapes. We can move both tapes in the same direction, so the difference between their two positions will be 0. We can move the input tape back and the output tape forward, which will result difference between their positions of 2. There is no way we can move the tape heads so the difference between their positions is odd. So we can't reach situation where the read tape is at position n and the work tape is at position n+1 (For example position 1 for input tape and position 2 for output tape). How we do proceed then with the algorithm?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Very basic turing machines problem

    Hey mrproper.

    A question I have for you is what the structure of the Turing model is. You say you have an input and an output tape: in some models you only have one tape which you can read or write to but you have two tapes.

    So the question I have is where do you get the actual instructions from (is it on a separate tape), and also what kind of data can you have in working memory (i.e. what is the definition of the entire state-space mathematically of the Turing Machine)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Very basic turing machines problem

    Quote Originally Posted by chiro View Post
    So the question I have is where do you get the actual instructions from (is it on a separate tape), and also what kind of data can you have in working memory (i.e. what is the definition of the entire state-space mathematically of the Turing Machine)?
    See Multi-tape Turing machines.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    73
    Thanks
    2

    Re: Very basic turing machines problem

    I can't answer this question, I think. I'm complete novice in the matter and not completely sure exactly what You ask. But I can give you context - that is how I got to the question I ask and why I find it so important to stop reading and start thinking / asking questions. So...

    I started reading several things at once and got to the point where the idea that computational model doesn't matter is discussed. That is - it doesn't matter which model of a machine we use, if we want to find out if something is computable and to discover in which complexity class it belongs.

    So if it doesn't matter what machine we use to do computations, it can have only one input and one output/work tape; it can have one read only input tape and multiple work tapes; it can have different alphabet and even different movement commands for the tape heads. For example the classic texts seems to describe only two tape movements - "left" and "right" (or "back" and "forward" movement), while some texts like these notes (http://web.science.mq.edu.au/~chris/langmach/chap09.pdf) do discuss the possibility of third movement command which makes the tape head stay where it is ("no movement"). The notes mention that adding this third command does not make more powerful machine which can solve a problem that the other can't. (This is discussed within the context of a machine with one tape only though).

    So if it really doesn't matter, there must be an algorithm for the described two tape machine (one r/o input tape and one r/w output/work tape that can do the above operation. Only I couldn't find it. So I ask ...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    73
    Thanks
    2

    Re: Very basic turing machines problem

    I think I found an approach. You just move one of the tapes to the start symbol and try one more left (backward) movement after that. The difference between the positions of the two heads will be now odd number.
    Seems like cheating though.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Very basic turing machines problem

    Quote Originally Posted by mrproper View Post
    You just move one of the tapes to the start symbol and try one more left (backward) movement after that. The difference between the positions of the two heads will be now odd number.
    This is one possible way.

    More generally, the machine may have to remember (in its state) character(s) it read during previous step(s). I.e., there have to be several copies of one state, one per character read during one of the previous steps.

    Here is a possible execution trace. There is a loop during which the machine reads two characters and writes four characters; then it starts the next iteration of the loop.

    Code:
    (1) |ABC  (2) A|BC  (3) |ABC  (4) A|BC  (5) AB|C
        |         A|         AA|      A AB|     AA BB|
    I write step numbers in parentheses. What follows is the description of the machine before the corresponding step. The top line shows the input tape and the bottom line shows the work tape. I write "|" before the character that is observed by the head. Since "|" is not an actual character on the tape, ignore the spaces between characters; they are for alignment only.

    During step 1 the machine reads A and writes A on the work tape. It also remembers A in a state. Both heads move right. During step 2 the machine writes the character it remembered ("A") and not the one observed on the input tape. It also remembers the character it observes ("B"). The input head moves left and the work head moves right. During steps (3) and (4) the machine writes the latest remembered character ("B"); both heads move right.
    Thanks from mrproper
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    73
    Thanks
    2

    Re: Very basic turing machines problem

    That's it!!! Wow.
    The needed states will grow with the size of input, but since the input is finite, so the states...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Very basic turing machines problem

    The number of states will grow with the size of the input alphabet but not with the size of input.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    73
    Thanks
    2

    Re: Very basic turing machines problem

    Ok, I finally got that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2012, 07:23 AM
  2. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  3. Turing machines and decidability.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 29th 2010, 12:38 PM
  4. Turing machines with a single tape.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2010, 06:41 AM
  5. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 19th 2007, 03:39 PM

Search Tags


/mathhelpforum @mathhelpforum