search
Log In
0 votes
29 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.
in Theory of Computation 29 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
37 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 37 views
0 votes
0 answers
2
52 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 52 views
0 votes
0 answers
3
39 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 39 views
0 votes
0 answers
4
33 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 33 views
...