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?


1 Answer 1


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.

  • $\begingroup$ Basically find a verifier for S that proves membership for any valid input. $\endgroup$
    – NoName
    Mar 18, 2019 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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