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
-
$\begingroup$ Finding a language to reduce to would be useless. You want to reduce from a language that is known not to be recursive. $\endgroup$– StevenJan 9 at 21:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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}$.
