Show that the following language or problem is not recursive: $$ L=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\} $$ I was trying to prove it using reduction, but I cannot seem to find a language to reduce it to. I also tried it for the complement of L: $$ \overline{L}=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input }w, \exists q\in Q(M) \text{ such that } q \text{ is not visited}\} $$ And I still cannot find the solution. How should I approach this problem?
1 Answer
I'm assuming that $M$ is a decider and that by "all states" you are excluding the accepting and rejecting state.
Given a Turing machine $M$, you can build an equivalent Turing machine $M'$ that behaves like $M$ except that $M'$:
- has one additional state $q$ and one additional tape symbol $x$;
- whenever $M$ would accept/reject, $M'$ writes $x$ on the tape, goes through all the states of $M$ plus the additional state $q$, and then halts.
Since $M$ (with input $w$) halts if and only if $M'$ (with input $w$) uses all states, the language of the halting problem reduces to $L$, i.e., $L \not\in \mathsf{R}$.