# Decidable or Not: Set of all Turing Machines M that on input w uses all states of M

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?

• Finding a language to reduce to would be useless. You want to reduce from a language that is known not to be recursive. Jan 9, 2023 at 21:53

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