# Application of Generalized Rice's Theorem

I'm trying to understand how to apply the generalized Rice's theorem to prove that a problem is Turing-Recognizable.

Suppose that I have two TMs and I have to evaluate if there exists a string that both are able to accept.

Is this problem Turing-Recognizable?

Source of the theorem: https://cs.stackexchange.com/q/2322.

The problem is Turing-Recognizable because all the hyphotesis of the theorem hold.

$$w$$ = common string

1) $$L1=w, L2=w$$ then $$L2 \in RE$$

2) $$L1=w, L2=w$$ then $$L2 \in RE$$

3) $$w$$ is a finite language

• By saying "$w$ = common string" in your answer, you assume you know the string already. But the problem is to manage to find it. Also, $L_1\neq w$ and $L_2\neq w$. The problem is to see if there is a general method that, given any two languages $L_1$ and $L_2$, finds a $w$ such that $w\in L_1$ and $w\in L_2$. – frabala Mar 27 at 11:03
• I've understood your comment, but I'm still stuck. – gefavasej Mar 27 at 11:20

The problem is to show whether given a TM, $$M$$, we can recognize if it is a TM that given two TMs, $$M_1$$ and $$M_2$$, $$M$$ accepts iff $$L(M_1)\cap L(M_2)\neq\emptyset$$. The input of $$M$$ should consist of a tuple $$(\langle M_1 \rangle,\langle M_2 \rangle)$$ and $$M$$ should accept iff $$L(M_1)\cap L(M_2)\neq\emptyset$$.
Let $$S=\{L'~|~(\langle M_1\rangle,\langle M_2\rangle)\in L',~\text{iff}~L(M_1)\cap L(M_2)\neq\emptyset\}$$.
Then, according to the notation used in the link you give, $$L_S$$ is the class of languages that recognize encodings of TMs that can decide if two given TMs accept a common word. To show that the problem is Turing-recognizable is to show that $$L_S\in RE$$.
What can you say about $$S$$ and condition 1?
• For each language $L(M_1), L(M_2) \in S: L(M_1) \subseteq L(M_2)$ and $L(M_2) \subseteq L(M_1)$ because they accept the same string. – gefavasej Mar 28 at 15:00