Question

6. (10 points) Prove that the language L = {< M 1 , M 2 >: M, , M 2 are T M s and L(M-) = L(M 2)) is undecidable.

Answer 1

L = {<M1,M2>:M1,M2 ARE TMs an L(M1) = L(M2)} is undecidable.

Proof: We prove it by contradiction. We first assume that L is decidable,say the TM M_L decides L. We prove that A_TM is decidable. Similar as the previous solution, for each pair of M and x, we defined the function M_x . We also define the Turing machine M_c that accepts every string. Then we construct the Turning Machine M_ATM as follows,

• On input <M , x>.
• Construct the Turing machines <M_x , M_c>.
• Run M_L on the input <M_x , M_c>.
• If M_L  accepts the accept; if M_L rejects the reject.

Correctness : We prove correctness by two directions.

• If <M , x> ∈  A_{TM, e,g} , M accepts x. By the definition of  M_x , it accepts everything , which means L(M_x ) = Σ^* . Thus L(M_x ) = L(M_{c) .} Since M_Ldecides the language L, M_L must accept  <M_x , M_c>, Thus by the definition of  M_ATM ,it accepts <M , x>.
• If <M , x> ∈  A_{TM, e,g} , M does not accepts x. By the definition of  M_x, it accepts nothing ,which means  L(M_x ) = 0. Thus   L(M_x ) != L(M_{c) .} Since  M_Ldecides the language L, M_L must reject <M_x , M_c>, Thus by the definition of  M_ATM ,it rejects  <M , x>.

Combine these two cases, we show that  M_ATM decides   A_TM, which is a contradiction since we know that A_TM   is undecidable.