20. Reductions

Mar 15/17, 2022

• Reduction: problem $X$ is reduced to problem $Y$ => if we can solve $Y$ then we can solve $X$

• Language A is reduced to language B => there is a computable function $f$ (reduction) such that $w\in A\iff f(w)\in B$

Using reductions

Theorem 1: If language A is reduced to language B and language B is decidable, then A is decidable.

• Basic proof idea: Build the decider for A, using the decider for B, then, from reduction: $w\in A\iff f(w)\in B$

                     decider for A
          |=================================|
          |           |  f(w)   |  decider  |---> yes  M accepts w
   w ---> | reduction |-------->|   for B   |
          |           |         |           |---> no   M rejects w
          |=================================|
  

Theorem 2: Language A is reduced to B, and language A is undecidable, then B is undecidable.

• Basic proof idea: suppose B is decidable. Using the decider for B build the decider for A => contradiction
• To prove that B is undecidable, we only need to reduce a known undecidable language A to B

Theorem 3: If language A is reduced to $\bar{B}$ and language A is undecidable, then B is undecidable.

• If B is decidable, then $\bar{B}$ is decidable (see: complement)
• Basic proof idea: suppose B is decidable then $\bar{B}$ is decidable. Using the decider for $\bar{B}$ build the decider for A => contradiction

• $w\in A\iff f(w)\in \bar{B}$   (or alternatively: $w\in A\iff f(w)\notin B$ ) --- contradiction:

                     decider for A
          |=================================|
          |           |  f(w)   |  decider  |---> yes  M accepts w
   w ---> | reduction |-------->|   for !B  |
          |           |         |           |---> no   M rejects w
          |=================================|
  

• To prove that language B is undecidable, we only need to reduce a known undecidable language A to B or $\bar{B}$.

EX1. EQUAL${}_{DFA}$

EQUAL${}_{DFA}$ = { <$M_1$, $M_2$>: $M_1$ and $M_2$ are DFAs that accept the same language }

is reduced to: EMPTY${}_{DFA}$ = {<$M$>: $M$ is a DFA that accepts the empty language $\mathrm{\varnothing }$ }

To prove this, we only need to construct:

<$M_1$, $M_2$> => TM for reduction $f$ => $f(<M_1,M_2>)=<M>$ DFA

Then $<M_1,M_2>\in {\text{EQUAL}}_{DFA}\iff <M>\in {\text{EMPTY}}_{DFA}$ (T1)

Let $L_1$ be the language of DFA $M_1$ and let $L_2$ be the language of DFA $M_2$.

Construct DFA $M$ by combining $M_1$ and $M_2$ so that $L(M)=(L_1\cap \overline{L_2})\cup (\overline{L_1}\cap L_2)$

Then: $L_1=L_2\iff L(M)=\mathrm{\varnothing }$ and T1 holds.

                    decider for EQUAL_DFA
             |==================================|
             |           |   <M>    |  decider  |---> yes
<M1,M2> ---> | reduction |--------->|    for    |
             |           |          | EMPTY_DFA |---> no
             |==================================|

EX2. State-entry problem

• Input: Turing machine $M$, state $q$, string $w$
• Question: does $M$ enter state $q$ while processing $w$?
• Corresponding language: STATE${}_{TM}$ = { $<M,w,q>$: $M$ enters state $q$ on input $w$ }

Theorem: STATE${}_{TM}$ is undecidable

Proof. Reduce HALT${}_{TM}$ to STATE${}_{TM}$. Given the reduction, if STATE${}_{TM}$ is decidable, then HALT${}_{TM}$ is decidable => contradiction

                    decider for HALT_TM
             |==================================|
             |           | <M',q,w> |  decider  |---> yes
<M,w> -----> | reduction |--------->|    for    |
             |           |          | STATE_TM  |---> no
             |==================================|

We only need to build $<M,w>$ => reduction => $<\hat{M},q,w>$ so that $<M,w>\in {\text{HALT}}_{TM}\iff <\hat{M},w,q>\in {\text{STATE}}_{TM}$.

For the reduction, construct $\hat{M}$ from $M$:

• for all halting states in $M$, add transition $x\to x,R$ to special halt state $q$ where $x$ is a placeholder for every unused tape symbol $x$ of $q_i$.

• Then, if $M$ halts $\iff$ $\hat{M}$ halts on state $q$

Therefore: when $M$ halts on input $w$, then $\hat{M}$ halts on state $q$ on input $w$.
Equivalently: $<M,w>\in {\text{HALT}}_{TM}\iff <\hat{M},w,q>\in {\text{STATE}}_{TM}$.

EX3. Blank-tape halting problem

• Input: Turing machine $M$
• Question: Does $M$ halt when started with a blank tape?
• Corresponding language: BLANK${}_{TM}$ = { $<M>$: M is a Turing machine that halts when started on a blank tape }

Theorem: BLANK${}_{TM}$ is undecidable (blank tape halting problem is unsolvable)

Proof. Reduce HALT${}_{TM}$ (halting problem) to BLANK${}_{TM}$ (blank tape problem). Given this reduction, if BLANK${}_{TM}$ is decidable, then HALT${}_{TM}$ is decidable => contradiction

                    decider for HALT_TM
             |=================================|
             |           |   <M'>  |  decider  |---> yes
<M,w> -----> | reduction |-------->|    for    |
             |           |         | BLANK_TM  |---> no
             |=================================|

We only need to build the reduction $<M,w>$ => reduction => $<\hat{M}>$ so that $<M,w>\in {\text{HALT}}_{TM}\iff <\hat{M}>\in {\text{BLANK}}_{TM}$

Construct $<\hat{M}>$ from $<M,w>$:

• is tape blank?
  • N: accept and halt
  • Y: write $w$ on tape => run $M$ with input $w$
• => if $M$ halts then $\hat{M}$ halts also.

Therefore: if $M$ halts on input $w$ then $\hat{M}$ halts when started on blank tape.
Equivalently: $<M,w>\in {\text{HALT}}_{TM}\iff <\hat{M}>\in {\text{BLANK}}_{TM}$.

Undecidable problems for Recognizable Languages

See: Rice's theorem

Let $L$ be some Turing-recognizable language. All of these are undecidable: (1) is $L$ empty? (2) is $L$ regular? (3) does $L$ have size 2?

EX1. Empty language problem

• Input: Turing machine $M$
• Question: is $L(M)$ empty: $L(M)=\mathrm{\varnothing }$?
• Corresponding language: EMPTY${}_{TM}$ = { $<M>$: M is a Turing machine that accepts the empty language $\mathrm{\varnothing }$ }

Theorem: EMPTY${}_{TM}$ is undecidable (empty-language problem is unsolvable).

Proof. Reduce $A_{TM}$ (membership problem) to $\overline{{\text{EMPTY}}_{TM}}$ (empty language problem). Given the reduction, if $\overline{{\text{EMPTY}}_{TM}}$ is decidable, then $A_{TM}$ is decidable => contradiction.

We only need to build the reduction: $<M,w>$ => reduction => $<\hat{M}>$ so that $<M,w>\in {\text{A}}_{TM}\iff <\hat{M}>\in \overline{{\text{EMPTY}}_{TM}}$.

Construct $<\hat{M}>$ from $<M,w>$:

• let $s$ be input string: does $s$ equals $x$ (some arbitrary value x)?

  • Y: write $w$ on tape and simulate $M$ on $w$ => if $M$ accepts $w$, then accept $s$
  • for all other outcomes: reject

• When $M$ accepts $w$ => $L(\bar{M})=\{x\}\ne \mathrm{\varnothing }$

• When $M$ does not accept $w$ => $L(\hat{M})=\mathrm{\varnothing }$

Therefore: $M$ accepts $w\iff L(\bar{M})\ne \mathrm{\varnothing }$.
Equivalently: $<M,w>\in {\text{A}}_{TM}\iff <\hat{M}>\in \overline{{\text{EMPTY}}_{TM}}$.

EX2. Regular language problem

• Input: Turing machine $M$
• Question: is $L(M)$ a regular language?
• Corresponding language: REGULAR${}_{TM}$ = { $<M>$ : M is a Turing machine that accepts a regular language }

Theorem: REGULAR${}_{TM}$ is undecidable (regular language problem is undecidable)

Proof. Reduce $A_{TM}$ (membership problem) to $\overline{{\text{REGULAR}}_{TM}}$ (regular language problem). Given the reduction, if $\overline{{\text{REGULAR}}_{TM}}$ is decidable, then $A_{TM}$ is decidable => contradiction.

We only need to build the reduction $<M,w>$ => reduction => $<\hat{M}>$ so that $<M,w>\in A_{TM}\iff <\hat{M}>\in \overline{{\text{REGULAR}}_{TM}}$.

Construct $<\hat{M}>$ from $<M,w>$:

• let $s$ be input string: does $s=a^k{b}^k$ for some $k\ge 0$?

  • Y: write $w$ on tape and simulate $M$ on $w$ => if $M$ accepts $w$, then accept $s$
  • for all other outcomes: reject

• When $M$ accepts $w$ => $L(\hat{M})=\{a^n{b}^n:n\ge 0\}$ (not regular)

• When $M$ does not accept $w$ => $L(\hat{M})=\mathrm{\varnothing }$ (regular)

Therefore: $M$ accepts $w\iff L(\hat{M})$ is not regular.
Equivalently: $<M,w>\in A_{TM}\iff <\hat{M}>\in \overline{{\text{REGULAR}}_{TM}}$.

EX3. Size-2 language problem

• Input: Turing machine $M$
• Question: does $L(M)$ have size 2 ($|L(M)|=2$)?
• Corresponding language: SIZE2${}_{TM}$ = { $<M>$ : M is a Turing machine that accepts exactly 2 strings }

Theorem: SIZE2${}_{TM}$ is undecidable (size2 problem is unsolvable).

Proof. Reduce Reduce $A_{TM}$ (membership problem) to SIZE2${}_{TM}$ (size 2 language problem). Given the reduction, is SIZE2${}_{TM}$ is decidable, then $A_{TM}$ is decidable => contradiction.

We only need to build the reduction $<M,w>$ => reduction => $<\hat{M}>$ so that $<M,w>\in A_{TM}\iff <\hat{M}>\in {\text{SIZE2}}_{TM}$.

Construct $<\hat{M}>$ from $<M,w>$: - let $s$ be input string: does $s\in L$ for some $L$ accepting exactly 2 strings? - Y: write $w$ on tape and simulate $M$ on $w$ => if $M$ accepts $w$, then accept $s$ - for all other outcomes: reject

• When $M$ accepts $w$ => $L(\hat{M})$ = { Language of 2 strings }
• When $M$ does not accept $w$ => $L(\hat{M})=\mathrm{\varnothing }$   (0 strings)

Therefore: $M$ accepts $w\iff L(\hat{M})$ has size 2.
Equivalently: $<M,w>\in A_{TM}\iff <\hat{M}>\in {\text{SIZE2}}_{TM}$.