1. If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?

Solution by Arjun Suresh

Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$. Now, if $L'$ is $RE$, then there is a $TM$, which accepts and halts for all words not in $L$. So, if a word is given (either from $L$ or not from $L$), give it to both those $TM$s. If it is from $L$, the first $TM$ will halt and we say it belongs to $L$. If it is not from $L$, the second one will halt and we say it doesn't belong to $L$. Thus, $L$ becomes recursive.



blog comments powered by Disqus



This work is licensed under the CC By-SA 3.0 , without all the cruft that would otherwise be put at the bottom of the page.

Sister Sites: GATE CSE Wiki, GATE CSE, Aptitude Overflow