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 \Leftrightarrow 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 \Leftrightarrow 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 \(\overline{B}\) and language A is undecidable, then B is undecidable.

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

\(w \in A \Leftrightarrow f(w) \in \overline{B}\) (or alternatively: \(w \in A \Leftrightarrow 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 \(\overline{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 \(\emptyset\) }

To prove this, we only need to construct:

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

Then \(<M_1, M_2> \enspace \in \text{EQUAL}_{DFA} \Leftrightarrow \enspace <M> \enspace \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 \Leftrightarrow L(M) = \emptyset\) 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} \Leftrightarrow \enspace <\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 \rightarrow 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 \(\Leftrightarrow\) \(\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} \Leftrightarrow \enspace <\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} \Leftrightarrow \enspace <\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} \Leftrightarrow \enspace <\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) = \emptyset\)?
Corresponding language: EMPTY\(_{TM}\) = { \(<M>\): M is a Turing machine that accepts the empty language \(\emptyset\) }

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} \Leftrightarrow \enspace <\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(\overline{M}) = \{x\} \neq \emptyset\)
When \(M\) does not accept \(w\) => \(L(\hat{M}) = \emptyset\)

Therefore: \(M\) accepts \(w \Leftrightarrow L(\overline{M}) \neq \emptyset\).
Equivalently: \(<M,w> \in \text{A}_{TM} \Leftrightarrow \enspace <\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} \Leftrightarrow \enspace <\hat{M}> \in \overline{\text{REGULAR}_{TM}}\).

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

let \(s\) be input string: does \(s= a^kb^k\) for some \(k \geq 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^nb^n: n \geq 0 \}\) (not regular)
When \(M\) does not accept \(w\) => \(L(\hat{M}) = \emptyset\) (regular)

Therefore: \(M\) accepts \(w \Leftrightarrow L(\hat{M})\) is not regular.
Equivalently: \(<M,w> \in A_{TM} \Leftrightarrow \enspace <\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} \Leftrightarrow \enspace <\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}) = \emptyset\) (0 strings)

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