1. Undecidability via Mapping Reductions

A mapping reduction from a problem $X$ to a problem $B$ is a computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that $w\in A\iff f(w)\in B$.

$A{\le }_{m}B$ means $A$ is (mapping) reducible to $B$.

Theorem: if $A{\le }_{m}B$ and $B$ is decidable, then $A$ is also decidable

Proof:

1. Suppose that $A{\le }_{m}B$ and $B$ is decidable.
2. From (i), there is some computable function $f$ such that $w\in A\iff f(w)\in B$
3. From (ii) there is some sound, complete, and terminating machine $M_B$ such that $u\in B\iff M_B(i)=1$
4. Hence, we can construct a sound, complete, and terminating algorithm for $A$. $M_A(w)=M_B(f(w))$ It follows that: $w\in A\iff f(w)\in B\iff M_B(f(w))=1\iff M_A(w)=1$ As required.

Theorem: The Accepting Problem $A_{TM}$ is undecidable

Proof:

1. Since ${\text{HALT}}_{TM}$ is undecidable, it is sufficient to show that ${\text{HALT}}_{TM}{\le }_m{A}_{TM}$.
2. Given any input machine $M$, we construct a new machine $M^{\prime }$ prime that accepts when $M$ accepts and rejects, or otherwise when it does not terminate. Hence we have that $M^{\prime }(w)=1\iff M(w)=1\text{ or }M(w)=0$.
3. Hence, $⟨code(M),w⟩\in {\text{HALT}}_{TM}\iff ⟨code(M^{\prime }),w⟩\in A_{TM}$ Therefore our computable function for our reduction is given by $f(⟨code(M,w)⟩)=⟨code(M^{\prime }),w⟩$ Which we formalise as: $f(u)=\{\begin{array}{ll}⟨code(M^{\prime }),w⟩& \text{if }u=⟨code(M),w⟩\\ ϵ& \text{otherwise}\end{array}$

Theorem: The non-Emptiness Problem $\overline{E_{TM}}$ is undecidable

Proof:

1. Since $A_{TM}$ is undecidable, it is sufficient to show that $A_{TM}{\le }_m\overline{E_{T}M}$
2. Given any input machine $M$ and input word $w$, we construct a new machine $M_w$ as:

\text{Language}(M_w) \neq \emptyset &= 1 \Leftrightarrow M(w) = 1 \end{aligned}$3.Hencewehavethat:$\langle code(M), w \rangle \in A_{TM} \Leftrightarrow code(M_w) \in E_{TM}$Ourcomputablefunctionisgivenby$f(\langle code(M), w \rangle) = code(M_w)$Whichweformaliseas:$f(u) = \begin{cases} code(M_w) &\text{if } u = \langle code(M), w \rangle \ \epsilon &\text{otherwise} \end{cases}$$