Line 1: Line 1:
If L and L' are both recursively enumerable, then L is recursive. Why?
+
'''1.''' If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?
  
 
===Solution===
 
===Solution===
  
  
Given L is RE. So there is a TM, which accepts and halts for all words in L.  
+
Given <math>L</math> is RE. So there is a TM, which accepts and halts for all words in <math>L</math>.  
Now, if L' is RE, then there is a TM, which accepts and halts for all words not in L.
+
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 L or not from L,is given, give it to both those TMs. 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 L. Thus L becomes recursive.
+
So, if a word, from <math>L</math> or not from <math>L</math>,is given, give it to both those TMs. 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.
  
  
Line 12: Line 12:
 
{{Template:FB}}
 
{{Template:FB}}
  
 
+
{{subst:wikEd}}
  
  

Revision as of 16:57, 12 December 2013

1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?

Solution

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 TMs. 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.





{{subst:wikEd}}


blog comments powered by Disqus

1. If <math>L</math> and <math>L'</math> are both recursively enumerable, then <math>L</math> is recursive. Why?

Solution[edit]

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 TMs. 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.





{{subst:wikEd}}


blog comments powered by Disqus