search
Log In
0 votes
33 views

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$. 
in Theory of Computation
edited by
33 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
46 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$ codes for $TM’s$ that halt on no input. The set of all $TM$ codes for $TM's$ that halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
0 votes
0 answers
2
0 votes
0 answers
3
34 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 $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
4
31 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 31 views
...