Consider the language $L = \{\langle M_1,\ M_2 \rangle \mid \exists x : x \in L(M_1) \cap L(M_2)\}$. Show that $L$ is not decidable.
I'm attempting a proof by contradiction but I'm having trouble with the Turing machine part.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ What is a turning machine? You make it rotate? $\endgroup$– NathanielCommented Dec 9, 2023 at 0:18
-
$\begingroup$ (Machines for turning, for sure.) $\endgroup$– greybeardCommented Dec 9, 2023 at 13:10
-
$\begingroup$ Do you mean Turing machine? $\endgroup$– Henrik supports the communityCommented Dec 9, 2023 at 17:46
-
1$\begingroup$ Be nice, folks. Especially for a first post. $\endgroup$– Rick DeckerCommented Dec 10, 2023 at 1:57
-
$\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$– Pseudonym ♦Commented Dec 10, 2023 at 4:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Suppose you chose $M_1 = \Sigma^*$. Could you find a $M_2$ that would fill the bill here?
answered Dec 10, 2023 at 2:01