How to prove semi-decidable = verifiable?
-
29-09-2020 - |
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?
Solution
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:
- Let $S$ be an empty array (of turing machine emulations)
- For every $w\in\Sigma^*:$
- Add a new emulation of $V(x,w)$ to $S$.
- For every emulation $E\in S:$
- 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