0
$\begingroup$

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?

$\endgroup$
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$
    – Steven
    Jan 9 at 21:53

1 Answer 1

0
$\begingroup$

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}$.

$\endgroup$

Your Answer

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

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