How to prove semi-decidable = verifiable?

Question

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?

Answer 1

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^*:$
   3. Add a new emulation of $V(x,w)$ to $S$.
   4. For every emulation $E\in S:$
      5. 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