1. (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. Figure 1 illustrates this model. 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). . . Infinitely many rows Input String Infinitely many columns Figure 1: 2-Dimensional Turing Machine: In the 2DTM model, we have an infinite 2D grid, and a tape head that can move up and down (in addition to left and right). The input starts out contiguously at an arbitrary row and column, and the tape head starts at the first symbol of the input. 2. (10 points) Recall that from homework 4 the DROP OUT operation: DROP-OUT(L) = {w = xz(x, ze >" , ryz ( A for some y E >} It is the set of all strings w that would be in L, except that they are missing a single character y. Put another way, there exists a way to split w into two substrings zz and then insert y in between rz, with the resulting string xyz E L. However, we only receive w as input. We don't know how w should be split up into ry, we don't know what missing character y can be inserted in between zz to create a string ryz E L. As an example, let L = {abc, 123}. Then DROP-OUT(L) = {ab, ac, be, 12, 13,23 } And if L were an infinite language then DROP-OUT(L) would also be infinite. Prove that Turing-recognizable languages are closed under the DROP OUT operation