Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Turing machine! problem to getting startet

  1. Mar 11, 2013 #1
    Good everning!

    I am currently working on problems related to turing machines.

    Lets say we have a turing machine T . Vi can see the Turing machine driving in state 1, state 2 and so forth. If we do this we can set it up as a table. see under.

    in my head it will look like this (R is a marked square, this is the square that is read from and written to)

    x x x x x R x x x
    x x x x x x R x x
    x x x x x x x R x
    x x x x x x R x x
    x x x x x R x x x
    x x x x R x x x x
    x x x R x x x x x
    x x x x R x x x x
    x x x R x x x x x

    what in the table above ansver to the tape in the turing machine at a given time?

    With regards to a Turing machine, time complexity is a measure of how many times the tape moves when the machine is started on some input. Space complexity refers to how many cells of the tape are written to when the machine runs.

    will time correspond to how many times the tape moves at an input at start? And how will i explain(calculate) this in the stated problem above?

    And space, will that be how many cells in the figure above that is written to? wont this then be the number of R's?

    I dont know how to attack this problem. Any tips and hints will be good.

    Also i want to say sorry for the language, i know it's bad :)

    Thanks to the people willing to take a look at this!

    And it dont know if this is the right place to post this post, but i did not find any better forums/places that corresponds to the problem stated above. '

  2. jcsd
  3. Mar 12, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    States are not positions on the tape.

    I don't understand that question.

    What do you mean "at start"? Time corresponds to the number of steps, which corresponds to the number of movements on the tape.
    No, just the length of the strip where an R appears at some point.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook