CSC 341: April 9, 2007

From CSWiki

Notes for the class session

Definition 5.20: Language $A$ is mapping reducible to language $B$ , written $A \le_m B$ , if there is a computable function $f: \Sigma^* \rightarrow \Sigma^*$ , where for every $\omega, \omega \in A \Longleftrightarrow f(\omega) \in B$ . The function $f$ is called the reduction of $A$ to $B$ .

Proving $A_\mathsf{TM} \not\le_m E_\mathsf{TM}$ . (Suppose $A_\mathsf{TM} \le_m E_\mathsf{TM}$ .)

The oracle Turing machine $A^\mathsf{TM}$ is recognizable.
$A_\mathsf{TM}$ is Turing recognizable. ${\overline E_\mathsf{TM}}$ is Turing recognizable, so (since $E_\mathsf{TM}$ is not decidable), $E_\mathsf{TM}$ is not Turing recognizeable.
Suppose $A_\mathsf{TM} \le_m EQ_\mathsf{TM}$ . Then $A_\mathsf{TM} \le_m {\overline E_\mathsf{TM}}$ , and $A_\mathsf{TM}$ is not Turing recognizable, a contradiction.

Therefore, $A_\mathsf{TM} \not\le_m E_\mathsf{TM}$ .

If $A \le_m B$ and $B \le_m C$ , then $A \le_m C$ .

If $A$ is Turing recognizable and $A \le_m {\overline A}$ then ${\overline A} \le_m {\overline {\overline A}}$ . ${\overline {\overline A}}$ is simply $A$ , so ${\overline A} \le_m A$ . By Theorem 5.28, ${\overline A}$ is Turing recognizable. So $A$ is co-Turing recognizable. Hence, by Theorem 4.22, $A$ is decidable.

[edit]

Study questions

Is mapping reducibility a reflexive relation? Justify your answer.
Show that every language that is mapping-reducible to $A TM$ is Turing-computable.
Show that $H A L T TM$ is mapping-reducible to $R E G U L A R TM$ .