E 5. A write-tuice 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,E.x(0. 1, 2h40, q cept, q eject, ), where Q is the set of states, including go, laccept Ireject, is the input alphabet x(0,1,2) is the tape alphabet (see below), q0 is the start state. qaccept is the accept state, g is the reject state, reject 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 (y, 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 I) 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 does some write-twice Turing machine, and vice-versa. E 5. A write-tuice 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,E.x(0. 1, 2h40, q cept, q eject, ), where Q is the set of states, including go, laccept Ireject, is the input alphabet x(0,1,2) is the tape alphabet (see below), q0 is the start state. qaccept is the accept state, g is the reject state, reject 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 (y, 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 I) 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 does some write-twice Turing machine, and vice-versa