Turing machine reduction task I am having trouble solving the following task:


  Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$
  
  Prove that $D$ is not decidable by reducing $$A_{\mathrm{TM}}=\{\langle T, w \rangle \mid \text{$T$ is a Turing machine and $T$ accepts $w$}\}$$ to $D$.


My solution and proof idea

(I am not sure if they are correct.) Assume that $D$ is decidable. Let $R$ be a decider for $D$ and $S$ for $A_{\mathrm{TM}}$. We know that $A_{\mathrm{TM}}$ is not decidable. However, if we manage to show it is decidable using $R$ as subroutine, we derive a contradiction and have therefore shown that $R$ is not decidable either.

Now I have got to a point where I do not know further because I have problems finding ways of showig the contradiction since I cannot see a connection between entering all states and accepting input $w$. If the TM enters all states, it is still unclear if the input is also accepted.

I guess I have to run R on a modification of $T$ so that I can derive a contradiction.
Given a TM $T$, consider the machine $T'$ which, on input $w$, simulates $T$ on $w$ and enters a special state $q$ if and only if has determined that $T$ accepts $w$. Note you can easily guarantee $T'$ never enters $q$ prior to $T$ accepting $w$. Moreover, you can make sure that, once $T'$ enters $q$, it starts to cycle between all its states indefinitely. (For instance, have $T'$ write a special tape symbol so it knows it is supposed to do so.)

For an arbitrary $T$, producing the description of $T'$ is computable. I'll leave it to you to fill in the gaps so this is a full-fledged reduction.



As a rule of thumb, these exercises can usually be solved by producing description of machines (in this case, $T'$) which encode the answer to the original problem ($A_{\mathrm{TM}}$) in their own behavior. In this particular case, the idea is to establish the equivalence between $T'$ entering all its states and $T$ accepting $w$.