2. [20 points] 2-dimensional Turing machine A 2-dimensional Turing machine has an infinite "chessboard as its storage device (one cell for every address (i,j) Zx Z). Instead of L and R, there are 4 options for the head to move: Left (i--), Right (i++), Up (++), or Down (--). 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-dim TM M'. As with every TM, the 2-dimensional Turing machine starts with the input on its tape. To be specific, let's assume the input is written in positions (1,0),(2,0), ...,(n,0). Describe the moves of M' in plain English. For every possible move of M, you have to design a sequence of moves of M' that simulate M. Hint: Your simulation does not have to be efficient. You may store information about any nonempty cell of M anywhere and in any for- mat on the tape of M'. But you have to make sure that your stored information is consistent and can be found by M