6
$\begingroup$

Can anyone explain why can't we use a Turing machine's transition diagram? For e.g. The definition of a USELESSTM is as follow:

A useless state in a TM is one that is never entered on any input string.

USELESSTM = { ⟨ M, q⟩ ∣ q is a useless state in M }

I know this problem can be proved to be undecidable by reducing ETM to it, but I want to know why can't we do a breadth first search of the Turing machine's state diagram to find states that are unreachable. Then based on whether or not we found any unreachable states, we can say that there are or there are not any useless states.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Your proposed algorithm finds some useless state, but not all of them.

Remember that you have tape content to deal with. Say, for instance, a state is reachable when there's a symbol 2 on the tape. It is reachable in the state graph, but if the TM gets only binary input (and never write a 2 itself) it will never be attained by the machine.

The proof you have tells you that there is no way to fix this.

Note that this problem is similar to detecting dead code; maybe this metaphor works better for you.

Improve this answer
$\endgroup$
4
  • $\begingroup$ BFS are used to check for unreachable nodes in a DFA. So I dont think your argument is fair. Cause then they cannot be used to find unreachable nodes for DFA as well. $\endgroup$
    – Shashank
    Commented Dec 4, 2016 at 2:48
  • 1
    $\begingroup$ Sorry, got it. If the tape alphabets and the input alphabets are different, then and I don't write the specific tape alphabet that leads me to that state then I won't ever be able to reach it,even though there is a transition available for it. $\endgroup$
    – Shashank
    Commented Dec 4, 2016 at 2:59
  • $\begingroup$ @Shashank That's only an example; the "pattern" can be far more complex. Ultimately, asking whether the sole final state is reached is asking for whether whether the TM (ever) halts -- that's far beyond any cute little observation like symbols that never occur (which are really just the same as useless states). $\endgroup$
    – Raphael
    Commented Dec 4, 2016 at 10:55
  • 1
    $\begingroup$ @Shashank I believe Raphael's argument holds even when the alphabets are the same. Consider that you could have a state that is reachable only if you read $01$ and then a $1$ going backwards. This is impossible unless the head of the TM overwrites the first $0$ with a $1$ in the first step, but the TM might never do that and hence said state would be useless even though there exists the transitions that reach it. $\endgroup$
    – Bakuriu
    Commented Dec 4, 2016 at 10:56
2
$\begingroup$

A state $q$ in a Turing machine $M$ with start state $q_0$ is useless if there exists no input $w$ and no configuration $u_1qau_2$ such that we can reach $u_1qau_2$ when starting in configuration $q_0w$.

Intuitively, to find a useless state, we would need to explore not the finite transition diagram of $M$ but all possible computations of $M$ that begin with a starting configuration $q_0w$.

More precisely, we can reduce the emptiness problem for Turing machines to that of asking if a given state is useless. To do this, given a machine description $\langle M \rangle$, we simply ask if the state $q_{\mathrm{accept}}$ is useless for $M$. This is the case iff $L(M) = \emptyset$. Since the emptiness problem is not Turing-recognizable, neither is the useless-state problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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