A deterministic two-dimensional Turing machine is like a Turing ma chine except that instead of a one-dimensional tape it has a two- dimensional tape that is like a chessboard, infinite in all directions. It has a finite input alphabet and a finite tape alphabetcontain ing as a subset. Ifx * is the input, | = n, the machine starts in its start state s with x written in tape cells (0, 1), (0,2), . .. ' (0, n), the origin (0,0) containing a special symbol O E-Z, and all other cells (2,1) containing a special blank symbol u e-. It has a read/write head initially pointing to the origin. In each step, it reads the symbol ofcurrently occupying the cell it is scanning. Depending on that symbol and the current state of the finite control, it writes a symbol ofon that cell, moves one cell either north, south, east, or west, and enters a new state, according to its transition function . It accepts its input by erasing the entire board; that is, filling all cells with Give a rigorous formal definition of these machines, including a definition of configurations, the next configuration relation, and acceptance. Try to be as precise as possible. Your definition should begin as follows: "A two-dimensional Turing machine is a 7-tuple where Q is a finite set of states, A deterministic two-dimensional Turing machine is like a Turing ma chine except that instead of a one-dimensional tape it has a two- dimensional tape that is like a chessboard, infinite in all directions. It has a finite input alphabet and a finite tape alphabetcontain ing as a subset. Ifx * is the input, | = n, the machine starts in its start state s with x written in tape cells (0, 1), (0,2), . .. ' (0, n), the origin (0,0) containing a special symbol O E-Z, and all other cells (2,1) containing a special blank symbol u e-. It has a read/write head initially pointing to the origin. In each step, it reads the symbol ofcurrently occupying the cell it is scanning. Depending on that symbol and the current state of the finite control, it writes a symbol ofon that cell, moves one cell either north, south, east, or west, and enters a new state, according to its transition function . It accepts its input by erasing the entire board; that is, filling all cells with Give a rigorous formal definition of these machines, including a definition of configurations, the next configuration relation, and acceptance. Try to be as precise as possible. Your definition should begin as follows: "A two-dimensional Turing machine is a 7-tuple where Q is a finite set of states
