Question

5. Show this is undecidable: TMREJ = {(M, W) on input w, Turing machine M eventually enters the reject state }

Answer 1

Lets proof it by contradiction.

Lets assume There is a decider D for TM_REJ.

Now with that we can design an algorithm for Halting problem:

On input,turing machine M and input w:

   1. We run <M,w> on D,if D accepts means M reject w,so we will output yes as it is halting on rejecting.

   2. We design another turing machine M1 by interchanging the accepting and rejecting states of M.

      And then run <M1,w> on D,if D accpets means M1 rejects w,which implies M accepts w.So we will  

      output yes as it is halting on accepting.

3. Else we will output no as it is not halting.

So we see we can decide halting problem of turing machine by using the D.But we know halting problem is undecidable,so it is contradiction,no D can exists.

So TM_REJ is undecidable.