Question

Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q.

To prove that $S$ is semi-decidable, I've tried to use the equivalence:

Language $L$ over alphabet $\Sigma $ is semi-decidable $ \iff $ There exists a semi-decidable language $M$, such that $L = \{x \in \Sigma ^ \ast| \exists y \in \Sigma ^ \ast ⟨x,y⟩ \in M\} $.

Let $L_H = \{ ⟨M, q, x⟩ ∣ M$ runs on $x$ $\& $ $M$ reaches state $q \}$ and let $H(⟨M, q, x⟩)$ be a TM which decides $L_H$. If we simulate $M$ and $M$ runs on $x$ and reaches state $q$, then H accepts and $⟨M, q, x⟩ \in L_H$, therefore all words in $L_H$ are accepted by $H$ and $L_H$ is semi-decidable. Is it enough to show that $S$ is also semi-decidable? What are other common ways to prove a language is semi-decidable?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top