Excercise 3. (Reducing multitape NTMs) Now consider the non-deterministic two-tape Turing machine N = ({90, 91, qaccept, (reject}, {0,1}, {0, 1, U},8', 90, 9accept, Preject) with the transition function: 0 0 qo 1 qo du 90 0 1 q 0 91 1 0 91 Uu (91, 0, 0, R, R) (20,1, 1, R, R); (90,1,1, R, L) Paccept Paccept (90,1,0, L, L); (q1,0, 1, R, R) (90,1, 1, R, R) Preject C Adapt the algorithm for deterministic Turing machines in order to transform N into an equivalent non-deterministic single-tape Turing machine. Excercise 3. (Reducing multitape NTMs) Now consider the non-deterministic two-tape Turing machine N = ({90, 91, qaccept, (reject}, {0,1}, {0, 1, U},8', 90, 9accept, Preject) with the transition function: 0 0 qo 1 qo du 90 0 1 q 0 91 1 0 91 Uu (91, 0, 0, R, R) (20,1, 1, R, R); (90,1,1, R, L) Paccept Paccept (90,1,0, L, L); (q1,0, 1, R, R) (90,1, 1, R, R) Preject C Adapt the algorithm for deterministic Turing machines in order to transform N into an equivalent non-deterministic single-tape Turing machine