I am unable to understand this proof

L is recursively enumerable if and only if L is Turing recognizable

If anyone can prove this, that would be great help


1 Answer 1


If $L$ is recursively enumerable then, given $x \in \Sigma^*$, you can iterate over all $y \in L$ and check whether $x=y$. If that's the case accept, otherwise continue with the next $y$. After examining the last $y \in L$ (if any) reject. If $x \in L$, this procedure eventually accepts. If $x \not\in L$ this procedure either never halts or it rejects.

If $L$ is Turing recognizable by some TM $T$ then you can execute $T(x)$ for all $x \in \Sigma^*$ in a dovetail fashion. If $x \in L$, $T(x)$ will eventually halt and accept, and you can output $x$. If $x \not\in L$, $T(x)$ will either never halt or it will reject (and you ignore $x$).


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.