What language is accepted by a Turing machine which has a state that it does not enter on input I?


1.If the accept state is the state that it never enters then should L={empty}?

2.If the reject state is the state that it never enters then should L={everything}?

3.What if the TM has multiple accept/reject states?

4.What if the state that it never enters is neither the reject nor accept states? How does that affect L?

I have searched around and I have found a couple threads that helped prove that this problem is undecidable but is it Turing-recognizable? Co-Turing Recognizable? Both?


closed as unclear what you're asking by Hendrik Jan, Evil, David Richerby, fade2black, cody Dec 7 '17 at 16:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This problem is undecidable – which problem? You seem to be asking two different questions. The first, what is the semantics of TMs with useless states. The second, can we determine whether a TM has a useless state. The usual rule is one question per post. I only answered your first question. $\endgroup$ – Yuval Filmus Nov 27 '17 at 21:57

The definition of the language accepted by a Turing machine is valid for all Turing machines, whether they have useless states or not. Absolutely nothing changes. If there is a useless state, removing it wouldn't change the language accepted by the machine, as does adding another useless state.

Consider a similar question about C programs. What if I have a function which is never called? Does this affect the way the program executes? It doesn't.1 The same holds for Turing machines.

1Actually it might, since you might run out of memory a tiny bit faster.


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