Answer:
The Explanation have got it all Go through the explanations.
Explanation:
Define the decision problem with the language
USELESS TM = {hM, qi | q is a useless state in TM M }.
We show that USELESS TM is undecidable by reducing ETM to USELESS TM, where
ETM = { hMi | M is a TM and L(M) = ∅ }. We know ETM is undecidable by Theorem 5.2.
Assume that USELESS TM is decidable and that TM R decides it. Note that for any
Turing machine M with accept state qaccept, qaccept is useless if L(M) = ∅.
Thus, because TM R solves USELESS TM, we can use R to check if qaccept is a useless
state to decide ETM. Specifically, below is a TM S that decides ETM by using the
decider R for USELESS TM as a subroutine:
S = “On input hMi, where M is a TM:
1. Run TM R on input hM, qaccepti, where qaccept is
the acceptable state of M.
2. If R accepts, accept. If R rejects, reject.”
However, since we know that ETM is undecidable, there cannot exist a TM that decides
USELESS TM.
