P M is a Turing Machine and LM LM Is P decidable Why or why

P = {M is a Turing Machine and L(M)= L(M)*}. Is P decidable? Why or why not?

Solution

Answer: -

EQTM is of type NTR (see Theorem 5.K). We prove this by showing ATM m EQTM
and applying Corollary 5.I. Define the reducing function f(hM, wi) = hM1, M2i, where

M1 = “reject on all inputs.”
M2 = “On input x:
1. Ignore input x, and run M on w.
2. If M accepts w, accept.”
Note that L(M1) = . For the language of TM M2,
if M accepts w (i.e., hM, wi 6 ATM), then L(M2) = ;
if M does not accept w (i.e., hM, wi ATM), then L(M2) = .
Thus, if hM, wi is a YES instance for ATM (i.e., hM, wi ATM, so M does not accept w), then
L(M1) = and L(M2) = , which are the same, implying that f(hM, wi) = hM1, M2i EQTM
is a YES instance for EQTM. Also, if hM, wi is a NO instance for ATM (i.e., hM, wi 6 ATM,
so M accepts w), then L(M1) = and L(M2) =
, which are not the same, implying that
f(hM, wi) = hM1, M2i 6 EQTM is a NO instance for EQTM. Hence, we see that hM, wi ATM
f(hM, wi) = hM1, M2i EQTM, so ATM m EQTM. But ATM is not TM-recognizable
(Corollary 4.M), so EQTM i