DO NOT COPY. I can understand it and would not vote

Theory of Computation

(10 points) Define a 2D-Turing Machine (2DTM) to be a Turing Machine whose tape is an infinite 2-dimensional grid (rather than an infinite linear tape). When the machine transitions, it may move left, right, up, or down. The 2D grid starts with the input string on a single row, and the head starts on the first character of the input. Everything else is the same. Prove that a language is Turing- recognizable if and only if it is recognized by a 2DTM. (Hint: the 2DTM will only have a finite amount of non-empty rows in use at any given time). (10 points) Define a 2D-Turing Machine (2DTM) to be a Turing Machine whose tape is an infinite 2-dimensional grid (rather than an infinite linear tape). When the machine transitions, it may move left, right, up, or down. The 2D grid starts with the input string on a single row, and the head starts on the first character of the input. Everything else is the same. Prove that a language is Turing- recognizable if and only if it is recognized by a 2DTM. (Hint: the 2DTM will only have a finite amount of non-empty rows in use at any given time)