Theory of Computation: Lecture 6

From Hard Problems to Reductions

Concrete undecidable and unrecognizable languages, such as $A_{\mathrm{TM}}$ and $\overline{A_{\mathrm{TM}}}$, become tools once they can be transformed into other problems. Reductions turn one hard example into a method: to prove that a new problem is hard, show that a known hard problem can be translated into it.

Reduction. A transformation from instances of one decision problem to instances of another decision problem that preserves yes/no answers.

A reduction says: if I had a solver for the target problem, I could solve the source problem by translating the input first.

The direction matters. If $A$ reduces to $B$, then $B$ is at least as hard as $A$:

• if $B$ is decidable, then $A$ is decidable;
• if $A$ is undecidable, then $B$ is undecidable.

Example 1. DFA nonemptiness as reachability.

Let

$$NE_{\mathrm{DFA}}=\{\langle D\rangle\mid D\text{ is a DFA and }L(D)\ne\varnothing\}.$$

Let

$$L_{\mathrm{path}}=\{\langle G,v,w\rangle\mid G\text{ is a directed graph and there is a path from }v\text{ to }w\}.$$

Given a DFA $D=(Q,\Sigma,\delta,q_0,F)$, build a directed graph from its transition graph, ignore transition labels, add a fresh target vertex $t$, and add an edge $q\to t$ from every accepting state $q\in F$. Then:

$$L(D)\ne\varnothing \quad\Longleftrightarrow\quad \text{there is a path from }q_0\text{ to }t.$$

The transformation does not decide whether $D$ is nonempty. It only builds the graph instance. The path solver, if available, answers the translated question.

Mapping Reductions

To use reductions inside Turing-machine proofs, the transformation itself must be algorithmic.

Computable function. A total function $f:\Sigma^*\to\Sigma^*$ is computable if some Turing machine halts on every input $w$ with exactly $f(w)$ on its tape.

Totality is essential: the reduction must always finish producing the translated instance, even when the instance it produces contains a machine that may later loop.

Mapping reduction. A language $A$ is mapping reducible to a language $B$, written $A\le_m B$, if there is a computable function $f:\Sigma^*\to\Sigma^*$ such that for every string $w$,

$$w\in A \quad\Longleftrightarrow\quad f(w)\in B.$$

• Computability. The function $f$ can be produced by a decider-like TM that halts on every input.
• Correctness. Membership is preserved exactly, both for yes-instances and for no-instances.

The function need not be surjective. Some instances of $B$ may never appear as $f(w)$.

Theorem. If $A\le_m B$ and $B$ is decidable, then $A$ is decidable.

Proof. Let $M_B$ decide $B$, and let $f$ be a mapping reduction from $A$ to $B$. Construct a TM $N$:

1. On input $w$, compute $f(w)$.
2. Run $M_B$ on input $f(w)$.
3. Output whatever $M_B$ outputs.

$N$ halts because $f$ is computable and $M_B$ is a decider. Also,

$$N\text{ accepts }w \quad\Longleftrightarrow\quad M_B\text{ accepts }f(w) \quad\Longleftrightarrow\quad f(w)\in B \quad\Longleftrightarrow\quad w\in A.$$

So $N$ decides $A$.

Corollary. If $A\le_m B$ and $A$ is undecidable, then $B$ is undecidable.

Otherwise, a decider for $B$ would give a decider for $A$, contradicting the known undecidability of $A$.

Recipe: proving undecidability by mapping reduction.

1. Choose a known undecidable language $A$.
2. For an arbitrary input $w$ of $A$, construct an instance $f(w)$ of the target language $B$.
3. Prove that $f$ is computable. Usually this means showing that a TM can write down the code of the new machine without running it.
4. Prove the two cases: $w\in A\Rightarrow f(w)\in B$ and $w\notin A\Rightarrow f(w)\notin B$.
5. Conclude that $B$ is undecidable.

The reduction must translate instances, not solve the source problem while translating.

Undecidability Examples

The halting problem can be reproved cleanly as a mapping-reduction result. Use the notation

$$\mathrm{HALT}_{\mathrm{TM}}= \{\langle M,w\rangle\mid M\text{ is a TM and }M\text{ halts on }w\},$$

the same language previously denoted $\mathrm{HALT}$.

Theorem. $A_{\mathrm{TM}}\le_m\mathrm{HALT}_{\mathrm{TM}}$. Therefore $\mathrm{HALT}_{\mathrm{TM}}$ is undecidable.

Given $x=\langle M,w\rangle$, define

$$f(x)=\langle M',w\rangle,$$

where $M'$ is the following machine:

1. On input $y$, run $M$ on $w$.
2. If $M$ accepts $w$, accept $y$.
3. If $M$ rejects $w$, loop forever.

The function $f$ is computable because it only writes the code of $M'$ with $M$ and $w$ embedded inside it. It does not run $M'$.

If $\langle M,w\rangle\in A_{\mathrm{TM}}$, then $M$ accepts $w$, so $M'$ accepts every input, in particular $w$. Thus $\langle M',w\rangle\in\mathrm{HALT}_{\mathrm{TM}}$.

If $\langle M,w\rangle\notin A_{\mathrm{TM}}$, then $M$ either rejects or loops on $w$. In either case $M'$ does not halt on any input: it loops explicitly after rejection, or it waits forever for $M$ to halt. Thus $\langle M',w\rangle\notin\mathrm{HALT}_{\mathrm{TM}}$.

So $f$ is a mapping reduction from $A_{\mathrm{TM}}$ to $\mathrm{HALT}_{\mathrm{TM}}$. Since $A_{\mathrm{TM}}$ is undecidable, $\mathrm{HALT}_{\mathrm{TM}}$ is undecidable.

Regularity of TM languages.

$$REG_{\mathrm{TM}}= \{\langle N\rangle\mid N\text{ is a TM and }L(N)\text{ is regular}\}.$$

Unlike $E_{\mathrm{DFA}}$ or $EQ_{\mathrm{DFA}}$, this problem asks a property of a Turing machine's language. The machine itself is finite, but the language it accepts may be non-regular, undecidable, or only recognizable.

Theorem. $REG_{\mathrm{TM}}$ is undecidable.

Reduce from $A_{\mathrm{TM}}$. Let

$$B=\{0^n1^n\mid n\ge 0\},$$

which is non-regular. Given $x=\langle M,w\rangle$, output $f(x)=\langle M'\rangle$, where $M'$ is:

1. On input $y$, if $y\in B$, accept.
2. Otherwise, run $M$ on $w$.
3. Accept $y$ iff $M$ accepts $w$.

The test $y\in B$ is decidable by a Turing machine: check that the input has the form $0^*1^*$ and that the two block lengths match.

If $\langle M,w\rangle\in A_{\mathrm{TM}}$, then $M$ accepts $w$. Every $y\in B$ is accepted by step 1, and every $y\notin B$ is accepted by step 3. Hence

$$L(M')=\{0,1\}^*,$$

which is regular.

If $\langle M,w\rangle\notin A_{\mathrm{TM}}$, then $M$ does not accept $w$. The only strings accepted by $M'$ are the strings caught by step 1, so

$$L(M')=B,$$

which is non-regular.

Thus

$$\langle M,w\rangle\in A_{\mathrm{TM}} \quad\Longleftrightarrow\quad \langle M'\rangle\in REG_{\mathrm{TM}}.$$

So $A_{\mathrm{TM}}\le_m REG_{\mathrm{TM}}$, and $REG_{\mathrm{TM}}$ is undecidable.

Recognizability and Equality of TM Languages

The same pipeline works for recognizers, but the conclusion is weaker because recognizers may loop on no-instances.

Theorem. If $A\le_m B$ and $B$ is recognizable, then $A$ is recognizable.

Let $R_B$ recognize $B$, and let $f$ reduce $A$ to $B$. On input $w$, compute $f(w)$ and run $R_B$ on $f(w)$. The resulting machine accepts exactly when

$$w\in A \quad\Longleftrightarrow\quad f(w)\in B \quad\Longleftrightarrow\quad R_B\text{ accepts }f(w).$$

If $w\notin A$, then $f(w)\notin B$, so $R_B$ may reject or loop. That is allowed for recognizers.

Corollary. If $A\le_m B$ and $A$ is unrecognizable, then $B$ is unrecognizable.

TM language equivalence.

$$EQ_{\mathrm{TM}}= \{\langle M_1,M_2\rangle\mid M_1,M_2\text{ are TMs and }L(M_1)=L(M_2)\}.$$

For DFAs, equivalence was decidable by product construction and reachability. For Turing machines, equality of recognized languages is not even recognizable.

Theorem. $EQ_{\mathrm{TM}}$ is unrecognizable.

Use the known unrecognizable language $\overline{A_{\mathrm{TM}}}$. Given $x=\langle M,w\rangle$, construct

$$f(x)=\langle M_1,M_2\rangle$$

where:

Machine $M_1$. On input $y$, run $M$ on $w$. If $M$ accepts $w$, accept $y$. If $M$ rejects $w$, loop forever.

Machine $M_2$. On input $y$, reject.

If $\langle M,w\rangle\in\overline{A_{\mathrm{TM}}}$, then $M$ does not accept $w$. The machine $M_1$ accepts no string, and $M_2$ also accepts no string. Hence

$$L(M_1)=\varnothing=L(M_2),$$

so $\langle M_1,M_2\rangle\in EQ_{\mathrm{TM}}$.

If $\langle M,w\rangle\notin\overline{A_{\mathrm{TM}}}$, then $M$ accepts $w$. The machine $M_1$ accepts every input, while $M_2$ accepts none:

$$L(M_1)=\Sigma^* \quad\text{and}\quad L(M_2)=\varnothing.$$

So $\langle M_1,M_2\rangle\notin EQ_{\mathrm{TM}}$.

Therefore

$$\overline{A_{\mathrm{TM}}}\le_m EQ_{\mathrm{TM}}.$$

Since $\overline{A_{\mathrm{TM}}}$ is unrecognizable, $EQ_{\mathrm{TM}}$ is unrecognizable. In particular, it is undecidable.