Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) (→{{Template:Author|Arjun Suresh|{{arjunweb}} }}) |
||
Line 6: | Line 6: | ||
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 is given (either from <math>L</math> or not from <math>L</math>), give it to both those $TM$s. If | + | So, if a word is given (either from <math>L</math> or not from <math>L</math>), 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 <math>L</math>. Thus, <math>L</math> becomes recursive. |
<!-- | <!-- | ||
=='''2.''' CYCLE(L) ={xy | yx is in L,L is regular } == | =='''2.''' CYCLE(L) ={xy | yx is in L,L is regular } == |
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 is given (either from <math>L</math> or not from <math>L</math>), 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 <math>L</math>. Thus, <math>L</math> becomes recursive.
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 is given (either from <math>L</math> or not from <math>L</math>), 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 <math>L</math>. Thus, <math>L</math> becomes recursive.