- #1
Tony11235
- 255
- 0
Homework Statement
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.
Homework Equations
None.
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: