in Theory of Computation
315 views
1 vote
1 vote
Consider statements
S1: The language of all TM’s that accept nothing is a Recursive enumerable language.
S2:Complement of the language of all TM's that accept nothing is also Recursive enumerable language.
Which of the statements are TRUE?
in Theory of Computation
by
315 views

3 Comments

S1 : False

S2 : True
2
2
can i say S2 is language of all the turing machine  which accept something ??
0
0
Yes, you can
1
1

1 Answer

1 vote
1 vote

Note: Any language accepted by TM is called recursively enumerable language.

For S1 we need to try infinite number of strings in a TM to determine that it accepts nothing. So, language is not recursively enumerable. Hence, FALSE.
For S2 we only need to find a single string that if accepts to show that it accepts something. Hence, TRUE.

Related questions