Question

Show that $E{Q}_{TM}{\text{'}}_{m}E{Q}_{TM}\text{'}$

Short answer

Answer:

The proof is given below.

Step-by-step solution

Turing Machine

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-zero. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

EQTM 'mEQTM

Let us understand about TM equality. Here,

$E{Q}_{TM}=\left\{\right(<M>,<N>):M,N$are Turing Machine and language $L\left(M\right)=L\left(N\right)\}$

$E{Q}_{TM}=\left\{\right(<M)>,<N>):M,N$are Turing Machine and language $L\left(M\right)=L\left(N\right)\}$,

Now, $E{Q}_{TM}\text{'}{}_{M}E{Q}_{Tm}meansthatE{Q}_{TM}isnotmapreducibletoE{Q}_{TM}$

We will first prove that is not Turing Recognizable.

1. We know that A' $mB$: if and only if both A and B are Turing Recognizable or Not-Turing Recognizable.

2. Now, in our prolem $E{Q}_{T{M}_{}}$, is complement to $E{Q}_{TM}$.

   Thus, if is $E{Q}_{TM}$Turing Recognizable then $E{Q}_{TM}$will not be Turing Recognizable and vice versa.

From (1) and (2), we can conclude that is not map reducible to $E{Q}_{TM}$, i.e,

$E{Q}_{TM}\text{'}{}_{M}E{Q}_{TM}$