E 5. A write-twice Turing machine is a Turing machine which can write to each cell of the tape at most twice. Formally, it is a 7-tuple (Q., {0.1.2), q0, qaccept, reject, ), where Q is the set of states, including go, Jaccept, Ireject is the input alphabet. {0, 1,2 is the tape alphabet (see below) qo is the start state, Zaccept is the accept state, greject is the reject state, 8: (Q\ F) Q {L, R} is the transition function As compared with a regular Turing machine, we modify the tape alphabet so every cell of the tape stores (,n) for some E, n E {0. 1.2). The character is the symbol that would appear on the tape of a normal Turing machine. The integer n is the cell's "count," i.e., the number of times that the machine has written to the cell Initially, the tape contains the input string and blanks as with a normal Turing machine, with all counts set to 0. Each computation step is just as with a normal Turing machine (note that the transition function only "sees" the-symbol stored at the current cell, not the count), but when the machine writes to a cell, its count is automatically incremented only if the character (from) in the cell changes. If the machine ever attempts to write to a cell whose count is already 2, the computation aborts and the result of the computation is undefined (neither accept, nor reject, nor loop) Show that write-twice Turing machines are equivalent in power to regular Turing machines That is, if some regular Turing machine decides a language L, then so docs some write-twice Turing machine, and vice-versa E 5. A write-twice Turing machine is a Turing machine which can write to each cell of the tape at most twice. Formally, it is a 7-tuple (Q., {0.1.2), q0, qaccept, reject, ), where Q is the set of states, including go, Jaccept, Ireject is the input alphabet. {0, 1,2 is the tape alphabet (see below) qo is the start state, Zaccept is the accept state, greject is the reject state, 8: (Q\ F) Q {L, R} is the transition function As compared with a regular Turing machine, we modify the tape alphabet so every cell of the tape stores (,n) for some E, n E {0. 1.2). The character is the symbol that would appear on the tape of a normal Turing machine. The integer n is the cell's "count," i.e., the number of times that the machine has written to the cell Initially, the tape contains the input string and blanks as with a normal Turing machine, with all counts set to 0. Each computation step is just as with a normal Turing machine (note that the transition function only "sees" the-symbol stored at the current cell, not the count), but when the machine writes to a cell, its count is automatically incremented only if the character (from) in the cell changes. If the machine ever attempts to write to a cell whose count is already 2, the computation aborts and the result of the computation is undefined (neither accept, nor reject, nor loop) Show that write-twice Turing machines are equivalent in power to regular Turing machines That is, if some regular Turing machine decides a language L, then so docs some write-twice Turing machine, and vice-versa