Register to reply 
Turing machine problem 
Share this thread: 
#1
Apr1107, 08:58 AM

P: 276

1. The problem statement, all variables and given/known data
A twodimensional Turing machine has the usual finitestate control but a tape that is a twodimensional 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 twodimensional 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. 


#2
Apr1307, 05:57 PM

P: 1,367

Would it make sense to map the twodimensional tape into a one dimensional tape, afterwhich, the result follows?



Register to reply 
Related Discussions  
Turing machine help!  Engineering, Comp Sci, & Technology Homework  0  
Complement of Universal Turing Machine  Does this exist?  Set Theory, Logic, Probability, Statistics  4  
Turing machine applied to virtual reality  General Discussion  7  
Paper Tape Turing Machine  Calculus & Beyond Homework  9  
Turing machines  Calculus  5 