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}}\).