The Gateway to Computer Science Excellence
+1 vote

Assume statements $S_1$ and $S_2$ defined as:

$S_1$: $L_2 – L_1$ is recursive enumerable where $L_1$ and $L_2$ are recursive and recursive enumerable respectively.

$S_2$: The set of all Turing machines is countable.

Which of the following is true?

  1. $S_1$ is correct and $S_2$ is not correct
  2. Both $S_1$ and $S_2$ are correct
  3. Both $S_1$ and $S_2$ are not correct
  4. $S_1$ is not correct and $S_2$ is correct
in Theory of Computation by Veteran (105k points)
recategorized by | 724 views

3 Answers

+1 vote
Best answer
  • S2 is correct: The set of all Turing machines is countable.
  • S1 s also TRUE. $L_2 - L_1 = L_2 \cap L_1'$. Since $L_1$ is recursive $L_1'$ is also recursive and hence r.e. also. And finally r.e. languages are closed under intersection.

So answer is B Both are correct

by Boss (33k points)
selected by
+3 votes
S1 is : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.


and ans is B both are correct

set of turing machines is countable but the set of all languages are uncountable
by Boss (49.3k points)
+1 vote

Answer : Both S1 and S2 are correct

Recursive enumerable Languages are not closed under set difference operation .But good thing about Statement S1 is as they mentioned that "L2–L1 is recursive enumerable where L1 and L2 are recursive enumerable respectively."

if L1 and L2 are Recursive enumerable then it is not sufficient to say that L2 - L1 will be Recursive enumerable  because it violates the closure property.but they have already mentioned that L2 - L1 is Recursive enumerable and along with that L1 and L2 are also recursive enumerable this statements would eliminate the possibilities to make this statement S1 wrong.

Reference : Recursively enumerable language

Statement S2 is also true which is "The set of all Turing machines is countable.".

Reference : Countable TM

by Boss (45.4k points)

@Sir...what is meaning of - " L2-L1 is RE, where L2 and L1 are RE.

Acc. to me -  It is given that ..L1 and L2 are RE, and now it is saying that L2-L1 will be RE.  

Please clear my doubt ..

@vijay i have written everything what is you doubt i did not understand .

a/c to my knowledge L2-L1 is set difference operation of language L2 and L1 which is RE (given in problem statement.). after they said L1 and L2 individually also RE.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,387 users