Question: A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.

Turing Machine

A Turing Machine is a computational model concept that runs on the unrestricted grammar of Type-0. It accepts recursive enumerable languages and comprises of an infinite tape length, where read and write operations can be performed accordingly.

Undecidable

A problem is undecidable if no Turing Machine exists, which will halt in a finite amount of time.

Define the given problem in the form of a language:

$USELES{S}_{TM}=\left\{\left(M,q\right)|whereqisuselessstateofTuringMachineM\right\}.$

To prove$USELES{S}_{TM}$is undecidable, use$E_{TM}$to reduce$USELES{S}_{TM}$as undecidable.

localid="1663253036066" $E_{TM}=\left\{\left(M\right)|MisaTuringMachineandL\left(M\right)=\varnothing \right\}$

It is known that$E_{TM}$is undecidable.

Let$USELES{S}_{TM}$be decidable and let R decide it.

For any state of Tuning Machine M, state$q_{accept}$is useless if$L\left(M\right)=\varnothing$

Now, use R to check whether$q_{accept}$is a useless state.

Define TM S, which decides$E_{TM}$by using the R for$USELES{S}_{TM}$as follows:

$S=onoutput\left(M\right)$, M being Turing Machine

• Run R on input $\left(M,q_{accept}\right)$
• If R accepts,$E_{TM}$accepts, if not, $E_{TM}$rejects.

But since$E_{TM}$is undecidable, so it is not possible to construct a Turing Machine that will decide $USELES{S}_{TM}$.

Hence, $USELES{S}_{TM}$is undecidable.