Consider always-halting non-deterministic TMs. Recall that such an NTM accepts an input x when at least one computation of M accepts x ; moreover, we assume that no computation of the NTM loops on any input. Now, let M be such an NTM and define M be the NTM obtained from M by exchanging the states q_acc and q_rej (leaving everything else and the transition function unchanged). Consider the claim : L(M)=L(M). Is it true or false? If you think it is true, prove it. If you think it is false, disprove it by giving a counterexample (which you must explain).