Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 4: | Line 4: | ||
| − | Given <math>L</math> is RE. So there is a TM, which accepts and halts for all words in <math>L</math>. | + | Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>. |
| − | Now, if <math>L'</math> is RE, then there is a TM, which accepts and halts for all words not in <math>L</math>. | + | Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>. |
| − | So, if a word, from <math>L</math> or not from <math>L</math>,is given, give it to both those | + | So, if a word, from <math>L</math> or not from <math>L</math>,is given, give it to both those $TM$s. If its from $L$, the first $TM$ will halt and we say it belongs to $L$. If its not from $L$, the second one will halt and we say it doesn't belong to <math>L</math>. Thus, <math>L</math> becomes recursive. |
1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?
Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>. Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>. So, if a word, from <math>L</math> or not from <math>L</math>,is given, give it to both those $TM$s. If its from $L$, the first $TM$ will halt and we say it belongs to $L$. If its not from $L$, the second one will halt and we say it doesn't belong to <math>L</math>. Thus, <math>L</math> becomes recursive.
1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?
Given <math>L</math> is $RE$. So there is a $TM$, which accepts and halts for all words in <math>L</math>. Now, if <math>L'</math> is $RE$, then there is a $TM$, which accepts and halts for all words not in <math>L</math>. So, if a word, from <math>L</math> or not from <math>L</math>,is given, give it to both those $TM$s. If its from $L$, the first $TM$ will halt and we say it belongs to $L$. If its not from $L$, the second one will halt and we say it doesn't belong to <math>L</math>. Thus, <math>L</math> becomes recursive.
GATECSE