A 2-dimensional Turing machine has an infinite 2-dimensional grid as its storage device (one cell for every address (i, j) ∈Z×Z). Instead of L and R, there are 5 options for the head to move from (i, j): Left (to (i −1, j), Right (to (i + 1, j)), Up (to (i, j + 1)), Down (to (i, j −1)), and Stay (remain at (i, j)) . Let us assume, that our 2-dimensional TM M has an additional 1- dimensional tape where the input is located as in a 1-tape TM. The 2-dimensional storage device contains a blank symbol in every cell at the start of the computation. Show that a 2-dimensional TM is not more powerful, i.e., every lan- guage accepted by a 2-dimensional TM M is accepted by one of our standard 1-dimensional TMs. You don’t have to simulate directly with a 1-tape TM, as you are allowed to use what we know about k-tape (1-dimensional) TMs without proof. Describe the moves of a simulating TM M ′ in plain English. For every possible move of M , you have to design a sequence of moves of M ′ that simulates that move of M .
A 2-dimensional Turing machine has an infinite 2-dimensional grid as
its storage device (one cell for every address (i, j) ∈Z×Z). Instead of
L and R, there are 5 options for the head to move from (i, j): Left (to
(i −1, j), Right (to (i + 1, j)), Up (to (i, j + 1)), Down (to (i, j −1)),
and Stay (remain at (i, j)) .
Let us assume, that our 2-dimensional TM M has an additional 1-
dimensional tape where the input is located as in a 1-tape TM. The
2-dimensional storage device contains a blank symbol in every cell at
the start of the computation.
Show that a 2-dimensional TM is not more powerful, i.e., every lan-
guage accepted by a 2-dimensional TM M is accepted by one of our
standard 1-dimensional TMs. You don’t have to simulate directly with
a 1-tape TM, as you are allowed to use what we know about k-tape
(1-dimensional) TMs without proof.
Describe the moves of a simulating TM M ′ in plain English. For every
possible move of M , you have to design a sequence of moves of M ′
that simulates that move of M .
Hints: Your simulation does not have to be efficient. You may store in-
formation about any nonempty cell of M anywhere and in any format
on the tape of M ′. But you have to make sure that your stored infor-
mation is consistent and can be found by M ′. The simulating TM M ′
might use coordinates to define locations on the 2-dimensional tape.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
