A two-dimensional Turing machine (2D TM for short) uses an infinite two-dimensional grid of cells as the tape. For simplicity assume that the tape cells corresponds to integers (i, j) with i,j 2 0; in other words the tape corresponds to the positive quadrant of the two dimensional plane. The machine crashes if it tries to move below the x = 0 line or to the left of the y 0 line. The transition function of such a machine has the form : Q Q {L, R, U, D, S} where L, R, U, D stand for "left", "right", "up" and "down" respectively, and S stands for "stay put". You can assume that the input to the 2D TM is written on the first row and that its head is initially at location (0, 0). Argue that a 2D TM can be simulated by an ordinary TM (1D TM); it may help you to use a multi-tape TM for simulation. In particular address the following points. C1..1 . How does your TM store the grid cells of a 2D TM on a one dimensional tape? .How does your TM keep track of the head position of the 2D TM? . How does your 1D TM simulate one step of the 2D TM? If a 2D TM takes t steps on some input how many steps (asymptotically) does your simulating 1D TM take on the same input? Give an asymptotic estimate. Note that it is quite difficult to give a formal proof of the simulation argument, hence we are looking for high-level arguments similar to those we gave in lecture for various simulations. A two-dimensional Turing machine (2D TM for short) uses an infinite two-dimensional grid of cells as the tape. For simplicity assume that the tape cells corresponds to integers (i, j) with i,j 2 0; in other words the tape corresponds to the positive quadrant of the two dimensional plane. The machine crashes if it tries to move below the x = 0 line or to the left of the y 0 line. The transition function of such a machine has the form : Q Q {L, R, U, D, S} where L, R, U, D stand for "left", "right", "up" and "down" respectively, and S stands for "stay put". You can assume that the input to the 2D TM is written on the first row and that its head is initially at location (0, 0). Argue that a 2D TM can be simulated by an ordinary TM (1D TM); it may help you to use a multi-tape TM for simulation. In particular address the following points. C1..1 . How does your TM store the grid cells of a 2D TM on a one dimensional tape? .How does your TM keep track of the head position of the 2D TM? . How does your 1D TM simulate one step of the 2D TM? If a 2D TM takes t steps on some input how many steps (asymptotically) does your simulating 1D TM take on the same input? Give an asymptotic estimate. Note that it is quite difficult to give a formal proof of the simulation argument, hence we are looking for high-level arguments similar to those we gave in lecture for various simulations