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.

My answer:

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

  • $\begingroup$ 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$. $\endgroup$ – frabala Mar 27 at 11:03
  • $\begingroup$ I've understood your comment, but I'm still stuck. $\endgroup$ – 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$.

You need to show that the three conditions hold (or that they don't).

What can you say about $S$ and condition 1?

  • $\begingroup$ 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. $\endgroup$ – gefavasej Mar 28 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.