turing machine problem


by Tony11235
Tags: machine, turing
Tony11235
Tony11235 is offline
#1
Apr11-07, 08:58 AM
P: 276
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.
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
e(ho0n3
e(ho0n3 is offline
#2
Apr13-07, 05:57 PM
P: 1,370
Would it make sense to map the two-dimensional 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