Show that $G_{u,v}$ is not decidable and not recognizable (nor is its complement)

93 Views Asked by At

Let $\Sigma$ be an alphabet, $u,v \in \Sigma^*, u \neq v$.

$G_{u,v} = \{ \langle M \rangle \mid M$ is turing machine, $u \in L(M) \Leftrightarrow v \in L(M)\}$.

I understand that if it is not recognizable then its also clearly not decidable. I guess by assuming it to be recognizable one can construct some impossible machine...

2

There are 2 best solutions below

2
On BEST ANSWER

One could also use Rogers's fixed point theorem (https://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem#Rogers's_fixed-point_theorem) to prove this, although the earlier answer is more general.

Assuming for a contradiction that $G_{u,v}$ were recognizable, say by a Turing machine $M_c$, then by Church's thesis (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Informal_usage_in_proofs), there is a recursive function $F$ such that for all $x$, $L\left(M_{F(x)}\right) = \{u\}$ if $M_c$ accepts $x$ and $L\left(M_{F(x)}\right) = \emptyset$ if $M_c$ does not accept $x$. By Rogers's fixed point theorem, there is some $x_0$ (in fact, infinitely many such $x_0$) such that $L\left(M_{F(x_0)}\right) = L\left(M_{x_0}\right)$.

Now we get a contradiction: if $M_c$ accepts $x_0$, then $L\left(M_{x_0}\right) = \{u\}$, but this implies $u \in L\left(M_{x_0}\right)$ and $v \notin L\left(M_{x_0}\right)$, contradicting the assumption that $x_0 \in L\left(M_c\right)$. If $M_c$ does not accept $x_0$, then $L\left(M_{x_0}\right) = \emptyset$, that is, $u \notin L\left(M_{x_0}\right)$ and $v \notin L\left(M_{x_0}\right)$, implying $x_0 \in L\left(M_c\right)$, which is again a contradiction.

2
On

Using Rice's theorem you may claim that it is not recognizable (as any machine accepting the empty set is in the language and this is a 'semantic' language, determined only by the languages of the Turing machines involved). For the other direction, to show that its complement is not recognizable, you can show a reduction from $A_{TM}$ to this language, that is, $$f(<M,w>)=N$$ such that on input $x\neq u$, $N$ accepts, and on input $u$, $N$ simulates the run of $M$ on $w$ and answers according to that run.