# Lecture 14: Reductions

## Decidability and Reductions

Definition: A function $f{\colon}\Sigma^\ast \to \Sigma^\ast$ is a reduction from language $A$ to language $B$ if $w\in A \Leftrightarrow f(w)\in B$ for every $w\in \Sigma^\ast$.

We say a function $f{\colon}\Sigma^\ast \to \Sigma^\ast$ is computable if there exists a Turing machine that for every input $w\in \Sigma^\ast$ halts with just $f(w)$ written on its tape.

We say $A$ reduces to $B$, denoted $A\le_m B$, if there exists a computable reduction from $A$ to $B$.

Theorem: If $A\le_m B$ and $A$ is undecidable, then so is $B$.

Proof: We prove the contrapostive. If $B$ is decidable, then $A$ is decidable. Suppose $M_B$ decides $B$ and $M_f$ computes $f$. Then, the following machine $M$ decides $A$:

Operation of $M$ on input $w$:

• Simulate $M_f$ on $w$ to compute $f(w)$.
• Simulate $M_B$ on $f(w)$.
• Accept if $M_B$ accepts and reject if $M_B$ rejects.

Since $f(w)\in B$ if and only if $w\in A$, the machine $M$ decides $A$.

## Example 1: Acceptance of Turing Machines

In lecture 13, we showed that the diagonal language ${L_{\mathrm{diag}}}$ for Turing machines is undecidable ${L_{\mathrm{diag}}}= \{ \langle M \rangle \mid \text{M on input \langle M \rangle rejects} \}.$ In lecture 12, we introduced the acceptance problem ${A_{\mathrm{TM}}}$ for Turing machines and showed that this language is recognizable (by a universal Turing machine).

Lemma: The acceptance problem for Turing machines is undecidable, ${A_{\mathrm{TM}}}= \{\langle M, w\rangle \mid \text{M on input w accepts} \}.$

Proof: We will show that ${L_{\mathrm{diag}}}\le_m {A_{\mathrm{TM}}}$. Consider the computable function that maps $M$ to $\langle M', w\rangle$, where $w=\langle M\rangle$ and $M'$ is a machine that accepts if and only if $M$ rejects. This function is a reduction from ${L_{\mathrm{diag}}}$ to ${A_{\mathrm{TM}}}$. Therefore, ${L_{\mathrm{diag}}}\le_m {A_{\mathrm{TM}}}$, which shows that ${A_{\mathrm{TM}}}$ is undecidable.

## Example 2: Non-emptiness

Lemma: The non-emptiness property for Turing machines is undecidable, ${\mathrm{\scriptstyle NON EMPTY}}= \{\langle M \rangle \mid L(M)\neq \emptyset \}.$

Proof: We will show ${A_{\mathrm{TM}}}\le_m {\mathrm{\scriptstyle NON EMPTY}}$. Consider the computable function $f$ that maps $\langle M, w\rangle$ to $\langle M_w \rangle$, where $M_w$ is the following machine:

Operation of $M_w$ on input $u$:

• If $u=w$, simulate $M$ on input $w$ and accept if $M$ accepts.
• If $u\neq w$, reject.

The language of $M_w$ is non-empty if and only if $M$ accepts $w$. Therefore, $f$ is a reduction from ${A_{\mathrm{TM}}}$ to ${\mathrm{\scriptstyle NON EMPTY}}$, which shows that ${\mathrm{\scriptstyle NON EMPTY}}$ is undecidable.

## Example 3: Halting Problem

Lemma: The halting problem for Turing machines is undecidable, ${\mathrm{\scriptstyle HALT}}= \{ \langle M,w \rangle \mid \text{M halts on input w} \}.$

Proof: We will show ${A_{\mathrm{TM}}}\le_m {\mathrm{\scriptstyle HALT}}$. Consider the computable function $f$ that maps $\langle M, w \rangle$ to $\langle M', w\rangle$, where $M'$ is the following machine:

Operation of $M'$ on input $u$:

• Simulate $M$ on $u$.
• Accept if $M$ accepts (but do not reject if $M$ rejects).

The machine $M'$ halts on some input $u$ if and only if $M$ accepts $u$. Therefore, $\langle M, w \rangle \in {A_{\mathrm{TM}}}$ if and only if $\langle M', w \rangle\in {\mathrm{\scriptstyle HALT}}$, which means that the function $f$ is a reduction from ${A_{\mathrm{TM}}}$ to ${\mathrm{\scriptstyle HALT}}$.