1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

  1. Apr 11, 2007 #1
    1. The problem statement, all variables and given/known data

    A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in the start state, as usual. Acceptance is by entering a final state, also as usual. Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary TM's.

    2. Relevant equations
    None.


    3. The attempt at a solution

    The problem COULD have something to do with injective mappings, but how use this to show the above...I am stuck.
     
    Last edited: Apr 11, 2007
  2. jcsd
  3. Apr 13, 2007 #2
    Would it make sense to map the two-dimensional tape into a one dimensional tape, afterwhich, the result follows?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Turing machine problem
  1. Turing machine help! (Replies: 0)

Loading...