1

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

gefavasej
  • 131
  • 5
  • 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 '19 at 11:03
  • I've understood your comment, but I'm still stuck. – gefavasej Mar 27 '19 at 11:20

1 Answers1

1

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?

frabala
  • 3,732
  • 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 '19 at 15:00