# Ullman (TOC) Edition 3 Exercise 9.3 Question 4 (Page No. 400)

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}$?

## Related questions

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$.
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.
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.
Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.