Is this language decidable or not? $$L_1 = \{ w \# x \mid w, x \in \{0, 1\}^∗ \text{ and $M_w$ visit all of non-final-states at least once for any $x$} \}$$
$M_w$ is the encoded turing machine.
sorry, this is my first time asking something here. 
I think it should be decidable, but i can't show any proof for that.
 A: If I understand you, the question is whether the following language is decideable: all strings $M\mathtt{\#}w$ such that $M$ is a Turing machine and $w$ is a word that makes $M$ go through all of its non-final states at least once.
We can prove that it's undecideable by reduction: Suppose you have a machine $R$ that decides whether a string is in the language or not.  Using $R$, you can decide undecideable problems— which shows that $R$ cannot exist.
Given $R$, we can define a decider $S$ for the undecideable halting problem. (The halting problem is: given a string $M\mathtt{\#}w$, decide whether $M$ halts on input $w$ or runs forever.) 
Define $S$ as follows:


*

*On input $M\mathtt{\#}w$,

*Define a Turing machine $M_w$ with a special non-final state called $\mathsf{Halted}$. The machine $M_w$ simulates machine $M$ on input $w$. During the simulation, it never visits state $\mathsf{Halted}$. If the simulation halts, $M_w$ visits all of its non-final states, including $\mathsf{Halted}$, then terminates. Otherwise, the simulation runs forever and never visits state $\mathsf{Halted}$.

*It follows that $R(M_w)$ is true if and only if $M$ halts when run on input $w$. $R(M_w)$ is false if $M$ runs forever on input $w$. Hence we return $R(M_w)$, and we've decided the halting problem.


Such a decider $S$ cannot exist, therefore the decider $R$ cannot either.
