An infinite grid Turing machine is a deterministic Turing machine that works with an infinite, two-dimensional grid instead of a single tape that is infinite to the right. Every achievable current position of the Turing machine is described as a pair of integers (x,y). As usual, the x-axis describes the horizontal direction and the y-axis the vertical direction. Initially, the cursor is located at the origin (0,0) and an input word of length n is written in the cells (0,0), (1,0), ..., (n-1,0); all other cells are blank (D). The transition function 8:Q xT+Q T {L,RU, D} allows to move one cell to the left, to the right, one cell up or one cell down. Otherwise, the machine is identical to the usual TM. Prove that infinite grid Turing machines are equivalent to Turing machines, i.e. show that they have the same set of recognizable languages. An infinite grid Turing machine is a deterministic Turing machine that works with an infinite, two-dimensional grid instead of a single tape that is infinite to the right. Every achievable current position of the Turing machine is described as a pair of integers (x,y). As usual, the x-axis describes the horizontal direction and the y-axis the vertical direction. Initially, the cursor is located at the origin (0,0) and an input word of length n is written in the cells (0,0), (1,0), ..., (n-1,0); all other cells are blank (D). The transition function 8:Q xT+Q T {L,RU, D} allows to move one cell to the left, to the right, one cell up or one cell down. Otherwise, the machine is identical to the usual TM. Prove that infinite grid Turing machines are equivalent to Turing machines, i.e. show that they have the same set of recognizable languages