Dimostrare un set è semi-decidibile

Question

Permettere $ S = {⟨m, q⟩ | ( esiste x) m $ raggiunge lo stato $ Q $ Quando si corre $ M $ Su $ x $$ } $, dove ⟨m, Q⟩ è codificato tm m e stato q.

Per dimostrarlo $ S $ è semi-dimettibile, ho provato a usare l'equivalenza:

Lingua $ L $ su alfabeto $ Sigma $ è semi-dimettibile $ iff $ Esiste un linguaggio semi-decidibile $ M $, tale che $ L = {x in Sigma ^ ast | esiste y in sigma ^ ast ⟨x, y⟩ in m } $.

Permettere $ L_h = {⟨m, q, x⟩ ∣ m $ gira su $ x $ $\& $ $ M $ raggiunge lo stato $ Q } $ e lascia $ H (⟨m, q, x⟩) $ essere un TM che decide $ L_h $. Se simuliamo $ M $ e $ M $ gira su $ x $ e raggiunge lo stato $ Q $, quindi H accetta e $ ⟨M, q, x⟩ in l_h $, quindi tutte le parole in $ L_h $ sono accettati da $ H $ e $ L_h $ è semi-dimettibile. È abbastanza per dimostrarlo $ S $ è anche semi-dimettibile? Quali sono gli altri modi comuni per dimostrare che una lingua è semi-riconoscibile?