Application of Generalized Rice's Theorem

105 Views Asked by At

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

1

There are 1 best solutions below

1
On

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?