4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Are you interested in the solution to the problem? $\endgroup$ – John L. Feb 26 '19 at 0:28
  • $\begingroup$ Not really, I kind of could solve the textbook's problem (proving the undecidability of TM with a useless state). What I'm thinking of now is just about the modification of a TM that has a useless state to a new TM without any useless state. Is it possible without just removing the useless state(s)? @Apass.Jack $\endgroup$ – inverted_index Feb 26 '19 at 0:32
  • $\begingroup$ What kind of operations is allowed in "modify this Turing Machine to another TM"? Do you actually mean "does there exist a Turing machine without useless states that accepts the same language"? Or do you actually mean "how to construct a Turing machine without useless states that accepts the same language"? $\endgroup$ – John L. Feb 26 '19 at 0:48
  • $\begingroup$ @Aspass.Jack I meant the latter one, actually. We don't have any information about what states are useless. Otherwise, as D.W. has posted, we could possibly just remove those states without changing the language. $\endgroup$ – inverted_index Feb 26 '19 at 1:02
4
$\begingroup$

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')\}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.