# How to prove semi-decidable = verifiable?

A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y)

A language is semi-decidable iff there is some Turing machine that accepts every string in L and either rejects or loops on every string not in L.

How can we show that the class of semi-decidable problems is equivalent to the class of verifiable problems? Or are they not?

– Jake
Jun 10, 2020 at 20:39

Its obvious why a semi-decidable language is verifiable ($$w$$ would be the machine's computation history on $$x$$). Now, we will show the other way:

Let $$V(x,w)$$ be a verifier for $$L$$. Define $$M(x)$$ as the following algorithm:

1. Let $$S$$ be an empty array (of turing machine emulations)
2. For every $$w\in\Sigma^*:$$
1. Add a new emulation of $$V(x,w)$$ to $$S$$.
2. For every emulation $$E\in S:$$
1. Compute one step for $$E$$. If, $$E$$ accepted, then accept.

This algorithm is correct, since if $$x\in L$$ then there is some $$w\in\Sigma^*$$ with $$V(x,w)=True$$ and therefore the algorithm will accept.

If the algorithm accepted, then there must be some $$w\in\Sigma^*$$ where $$V(x,w)=True$$ and thus $$x\in L$$ by definition