Question

Show that A_TM is not mapping reducible to E_TM. In other words, show that no computable function reduces A_TM to E_TM. (Hint: Use a proof by contradiction, and facts you already know about A_TM and E_TM.)

Short answer

To show A_TM is not map reducible toE_TM

Step-by-step solution

Defining Map Reducible

A language L₁ is mapping reducible to language L₂, if there exist a computable function f such that,

$f:{\sum }^{*}\to {\sum }^{*}$, where for all w

$w\in A\iff f\left(w\right)\in B$

It is expressed as $A{⩽}_{m}B$.

Proving that there exist no computable function reduces ATM to ETM

To prove it, assume that there is a function that reduces from A_TM to E_TM.

So, $A_{TM}{⩽}_m{E}_{TM}$through function f. So this means $w\in A_{TM}$only if $f\left(w\right)\in E_{TM}$. This also means $w\notin A_{TM}$if only $f\left(w\right)\notin E_{TM}$.

Now deduce similarly that $A_{TM}\text{'}{⩽}_m{E}_{TM}\text{'}$. But it’s well known that $E_{TM}\text{'}$ is Turing recognizable and A_TM is not Turing recognizable. This make assumption contradicts.

Hence, there exist no computable function reduces A_TM to E_TM.