Transforming TM with useless state(s)

I'm new to Computation Theory and trying to figure out the undecidability problems. Last night, I came up with the language of TM with a useless state:


$\text{USELESS_TM} = \{ \langle M, q \rangle\mid q\text{ is a useless state in TM }M\}$

where q is a state that M never enters on any input w. The problem is simply defined as: "determining whether a Turing machine has any useless states".

The question wanted me to show that this language is undecidable using a reduction argument. I thought it would be logical to reduce EMPTY_TM to USELESS_TM, and using contradiction show that if USELESS_TM is decidable, then EMPTY_TM will be decidable (which we know it's not).

I wanted to step a little bit forward in grasping the concepts of USELESS_TM. Is it possible to modify this Turing Machine to another TM M without useless states in such a way that L(USELESS) = L(M)? I thought about just removing the useless states, as the machine never gets into those states, so the language won't change. But, is there another way by like modifying a TM's definition to ensure that it has no useless states?

UPDATE . I borrowed the first example from Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Problems 5.13 --Textbook

This question is refreshing. Answers are given in the headers below.

There exists a Turing machine (TM) without useless states that accepts the same language as an arbitrary given TM.

Let TM $M=⟨Q,\Gamma, b,\Sigma, \delta, q_0, F⟩$ where
$$\delta: (Q\setminus F)\times \Gamma\not\to Q\times\Gamma\times\{L,R\}$$
is the transition function, where $L$ is left shift, $R$ is the right shift. For each state $q\in Q$, $q$ is either useful (reachable) or useless (non-reachable).
Let $Q'$ be the set of all useful states. Let $\delta'$ be the restriction of $\delta$ on $(Q'\setminus F)\times \Gamma$. Then we can check $M'=⟨Q',\Gamma, b,\Sigma, \delta, q_0, F\cap Q'⟩$ is a well-defined TM without useless states that accepts the same language as $M$.

Intuitively, $M'$ is simply $M$ with all useless states removed.

Exercise 3.19 indicates none of the following two languages is decidable.
$$\text{USELESS_STATES}=\{⟨M, g⟩\mid M \text{ is a TM with a useless state } g \}$$
$$\{⟨M, M'⟩\mid M \text{ is a TM and }M'\text{ is defined based on M as above} \}$$

No algorithm can produce a TM without useless states that accepts the same language as an arbitrary given TM.

For the sake of contradiction, suppose there is a such an algorithm $A$.

Let $M$ be a given TM. Applying $A$, we can construct another TM $M'$ without useless states that accepts the same language as $M$.

What is $F'$, the set of final states (a.k.a. accepting states) of $M'$?

• If $F'$ is empty, then $M'$ never accepts any word. That is, $L(M')$ is empty.

• If $F'$ is not empty, then $M'$ does accept some word since the states in $F'$ are reachable. That is, $L(M')$ is not empty.

Just by checking whether $F$ is empty or not, we will know whether $L(M')$ is empty or not. Since $L(M')$ is the same as $L(M)$, we will also know whether $L(M)$ is empty or not. Hence, we can decide whether $L(M)$ is empty or not.

However, it is well-known that it is undecidable to determine whether an arbitrary given TM accepts no words or not. This is a contradiction.

What we have used in the proof above is the following obvious property of TMs without useless states. Such a TM accepts at least one word if and only if it has at least one final state.

Intuitively, there is no algorithm to determine whether a final state in a TM is useless or not.

Here are two easy related exercise.

Exercise 1. Show the following language is not decidable.
$$\{⟨M⟩\mid M \text{ is a TM that accepts no words}\}$$

Exercise 2. Show the following language is not decidable.
$$\{⟨M, M'⟩\mid M \text{ is a TM and }\\ M' \text{ is a TM without useless states such that } L(M)=L(M')\}$$

StackExchange Computer Science Q#104834, answer score: 5