# Proving a set is semi-decidable

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?

You are missing a proof that $$L_H$$ is semi-decidable.
Here are two ways to prove that $$S$$ is semi-decidable.
First method. The following predicate is decidable: "$$M$$ reaches state $$q$$ after running on $$x$$ for $$t$$ steps". Hence the following is semi-decidable: "there exist $$x,t$$ such that $$M$$ reaches state $$q$$ after running on $$x$$ for $$t$$ steps".
Second method. On input $$M$$ and $$q$$, simulate $$M$$ on all possible inputs (by dovetailing); output $$\langle M,q \rangle$$ for each state $$q$$ reached by each of these simulations.