2
$\begingroup$

Given are two following languages:

$L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$

$L_2 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$

Are the languages decidable/undecidable/semi-decidable?

The intuition tells me that both languages cannot be decidable, for the simple reason that if any of them ends up in a loop, it can never be decided whether all states were visited. Is my way of thinking correct in both cases?

I would also say that $L_1$ is semi-decidable - in case all states were visited after some finite number of steps, we could decide the language and if not, we still won't be able to say anything about it.

Is it possible to reduce the halting problem to this problem to prove that it's not decidable?


Thank you!

$\endgroup$
  • $\begingroup$ Note: If both were semi-decidable, they would also both be decidable. Can you show why? $\endgroup$ – Raphael Sep 22 '17 at 5:45
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 22 '17 at 5:46
1
$\begingroup$

The first language is semidecidable while the second one is not semidecidable.

Claim 1: $L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$ is semidecidable.
Proof: On input $w\#x$ Simply simulate $M_w$ on $x$ and count the number of visited states. If the counter reaches $|Q|$ then ACCEPT. This shows $L_1$ is semidecidable/RE.

Claim 2: $L_2 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$ is not semidecidable.
Proof: Let $L_2$ be semidecidable. Then since $\overline{L}_1 = L_2$, i.e., $L_1$ and $L_2$ are complement of each other, $L_1$ (and so $L_2$) is decidable. In this case we can reduce the Halting problem to $L_1$ as following. Let $M$ be a Turing machine deciding $L_1$. We construct a Turing machine that decides the Halting problem. On input $w\#x$ we modify $M_w$ so that when $M$ halts, it first traverses all other states and then halts. We could do it by changing the ACCEPT state to a normal state, introducing a new ACCEPT state, and adding the following new transitions $$\delta(q_1, a) = q_2, \dots, \delta(q_n, a) = q_{new-accept}$$ where $a$ is a new alphabet symbol and when the modified $M_w$ is at the state $q_{old-accept}$ it first writes $a$ on the tape and enters the state $q_1$ (without moving the head, i.e, the head always reads $a$). Similarly for the the REJECT state. Thus $M_w(x)$ halts if and only if $M_w$ visits all states, which is decidable by $M$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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