edited by
273 views
0 votes
0 votes

Show that the following problems are not recursively enumerable:

  1. The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.
  2. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$.
  3. 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$. 
edited by

Please log in or register to answer this question.

Related questions

261
views
0 answers
0 votes
admin asked Jul 21, 2019
261 views
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.The set of all $TM$ codes for $TM's$ that halt on every input.The set of all $TM$ ... of all $TM$ codes for $TM's$ that fail to halt on at least one input.
191
views
0 answers
0 votes
admin asked Jul 21, 2019
191 views
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.
664
views
1 answers
0 votes
admin asked Jul 21, 2019
664 views
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes ... discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
185
views
0 answers
0 votes
admin asked Jul 21, 2019
185 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 ... $w$, never scans any tape cell more than once.