Reductions

An engineer and a mathematician are out for a walk and spot a house on fire. There is a garden hose lying in the yard; the engineer quickly hooks it up and puts out the fire.

They continue walking and see a home where a couple is washing a car in their driveway.

The mathematician detaches their hose and sets their house on fire, thus reducing the situation to a previously solved problem.

We proved that $A_\mathrm{TM}$ is undecidable using a tricky proof by contradiction. If we want to prove that other languages are undecidable, we can try to find similar tricks. But a simpler strategy is to leverage what we have already proved, a method known as reduction.

Definition

Given problems $P$ and $Q$ , we say that $P$ reduces to $Q$ , written

P \leq Q

if a solution to $Q$ would let us solve $P$ as well.

The notation is odd at first glance. The best way to think about $P \leq Q$ is that it refers to difficulty; $P$ is easier (or at least, no harder) than $Q$ if solving $Q$ also tells us how to solve $P$ .

Not surprisingly, any formal language that is harder to decide than an undecidable language is also undecidable.

Example

The language

\mathit{HALT} = \{\ \langle M,w\rangle\ |\ M \mathrm{~halts~on~input~} w\ \}

is semidecidable, but not decidable.

Proof of Semidecidability: To show that $\mathit{HALT}$ is semidecidable, we can just give the algorithm for a semidecider, namely:

def semidecide_Halt(M, w):
    simulate(M, w)
    return True

That is, a semidecider for $\mathit{HALT}$ can simulate the given machine on the given input. If this halts then (whether it accepts or rejects) the semidecider accepts the pair. If the machine runs forever on that input, the semidecider returns no answer.

Proof of Undecidability: We will show that $A_\mathrm{TM} \leq \mathit{HALT}$ , i.e. that if we could decide $\mathit{HALT}$ then we could decide $A_\mathrm{TM}$ . Since we know $A_\mathrm{TM}$ is not decidable, it follows that $\mathit{HALT}$ is not decidable either.

In other words, as soon as we prove that $\mathit{HALT}$ is at least as hard as the undecidable $A_\mathrm{TM}$ , we know that $\mathit{HALT}$ is undecidable too.

Here is why $A_\mathrm{TM} \leq \mathit{HALT}$ :

Suppose we could build a decider decide_Halt for $\mathit{HALT}$ .

Then we could build a decider decide_Atm for $A_\mathrm{TM}$ as follows:

def decide_Atm(M, w):
    if decide_Halt(M, w):
        return simulate(M, w)
    else:
        return False

That is, to correctly predict whether $M$ will accept $w$ , we first check whether $M$ will halt on $w$ . If so, we can run $M$ on $w$ and be sure we will see it accept or reject in a finite amount of time. If not, we know $M$ does not accept $w$ and can report that immediately.

Proving Reductions

Decidability Reduction Proofs ( $L_1\leq L_2$ )

What does a proof look like?

A typical decidability reduction proof that $L_1\leq L_2$ goes as follows:

Assume there is a decider for $L_2$ .
[Show an algorithm for deciding $L_1$ .]
Therefore $L_1$ reduces to $L_2$ . QED.

The direction is important. We assume the right-hand-side is decidable, and show that, if so, the left-hand-side is decidable.

Why is this useful?

A successful proof guarantees that

“if $L_2$ is decidable, then $L_1$ then is decidable.”

This direction is easiest to prove, but the logically equivalent contrapositive is more useful, namely

“if $L_1$ is not decidable, then $L_2$ is not decidable.”

This means that if we do a reduction proof where $L_1$ is a language like $A_\mathrm{TM}$ that we already know is not decidable, then our reduction proof guarantees that $L_2$ is not decidable.

For example, in the example above we proved that $A_\mathrm{TM} \leq \mathit{HALT}$ (i.e., if $A_\mathrm{TM}$ is not decidable, then $\mathit{HALT}$ is not decidable). It immediately follows that $\mathit{HALT}$ is not decidable. So then if we manage to prove $\mathit{HALT}\leq L'$ for some other language $L'$ , it will immediately follow that $L'$ is not decidable either. In this way, we can use reduction to prove that more and more languages are not decidable.

Example

A\mathrm{prime} := \{\ \langle M,w\rangle\ | \ M\mathrm{~accepts~} w \mathrm{~\&~} M\mathrm{'s~code~has~a~prime~number~of~states}\ \}

We can show $A\mathrm{prime}$ is undecidable by proving $A_\mathrm{TM} \leq A\mathrm{prime}$ .

Proof 1
Suppose there were a decider decide_Aprime for $A\mathrm{prime}$ . Then we could decide $A_\mathrm{TM}$ as follows:

Suppose we want to know if $\langle M,w\rangle\in A_\mathrm{TM}$ .\

Construct a TM $M'$ that is exactly like $M$ plus enough extra dummy/unreachable/useless states so that it has a prime number of states.

We haven’t changed the essential functionality of the TM, so $L(M) = L(M')$ , and $M$ accepts $w$ iff $M'$ accepts $w$ .
We can run decide_Aprime on $M'$ and $w$ to find out whether $M'$ accepts $w$ and has a prime number of states.
Since $M'$ has a prime number of states by construction, the result (true or false) tells us whether $M'$ accepts $w$ , and hence whether $M$ accepts $w$ .

Proof 2
Suppose there were a decider decide_Aprime for $A\mathrm{prime}$ . Then we could decide $A_\mathrm{TM}$ as follows:

Suppose we want to know if $\langle M,w\rangle\in A_\mathrm{TM}$ .

Let $n$ be the number of states in $M$ .
Construct TMs $M_0, M_1, \ldots, M_n$ such that $M_i$ is just like $M$ but with $i$ extra dummy/unreachable states.
A bit of number theory (for any $n\geq 1$ , there is a prime number between $n$ and $2n$ ) guarantees that at least one of the $M_i$ ’s has a prime number of states.
Run decide_Aprime on $M_i$ and $w$ for all $i\in 0..n$ .
If at least one answer is “yes” then $M$ accepts $w$ . Otherwise, $M$ does not accept $w$ .

Semidecidability Reduction Proofs ( $L_1\leq L_2$ )

What does a proof look like?

A typical semidecidability reduction proof that $L_1\leq L_2$ goes as follows:

Assume there is a semidecider for $L_2$ .
[Show an algorithm for semideciding $L_1$ .]
Therefore $L_1$ reduces to $L_2$ . QED.

Why is this useful?

A successful proof guarantees that

“if $L_1$ is not semidecidable, then $L_2$ is not semidecidable.”

This means that if we do a reduction proof where $L_1$ is a language like $\lnot A_\mathrm{TM}$ that we already know is not semidecidable, then our reduction proof guarantees that $L_2$ is not semidecidable.

What’s up with the notation?

Irritatingly, the notation $L_1\leq L_2$ and terminology ” $L_1$ reduces to $L_2$ ” can either mean “if $L_2$ is decidable then so is $L_1$ ” or “if $L_2$ is semidecidable then so is $L_1$ ,” and these are not equivalent statements. Context usually tells us which meaning is intended.

Reductions

Definition

Example

Proving Reductions

Decidability Reduction Proofs (L1≤L2L_1\leq L_2L1​≤L2​)

What does a proof look like?

Why is this useful?

Example

Semidecidability Reduction Proofs (L1≤L2L_1\leq L_2L1​≤L2​)

What does a proof look like?

Why is this useful?

What’s up with the notation?

Decidability Reduction Proofs ( $L_1\leq L_2$ )

Semidecidability Reduction Proofs ( $L_1\leq L_2$ )