search
Log In
0 votes
79 views

We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or non-RE?

  1. Does $L(M)$ contain at least two strings?
  2. Is $L(M)$ infinite?
  3. Is $L(M)$ a context-free language?
  4. Is $L(M) = (L(M))^{R}$?
in Theory of Computation 79 views

1 Answer

0 votes

Related questions

0 votes
0 answers
1
57 views
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$. The set of triples $(M_{1},M_{2},M_{3})$ such that $L(M_{1}) = L(M_{2})L(M_{3})$ ; i.e., the language of the first is the concatenation of the languages of the two $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 57 views
0 votes
0 answers
2
46 views
Show that the following questions are decidable: The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its tape. Hint: If $M$ has $m$ states, consider the first $m$ ... . The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
0 votes
0 answers
3
0 votes
0 answers
4
...