Mapping Reducibility for Proving Undecidability

From Diagonalization to Reducibility

Imagine you have a difficult problem, let's call it Problem A. You don't know how to solve it. However, you discover that if you had a magic box that could instantly solve a different problem, Problem B, you could use that box to solve Problem A. This relationship is called a reduction. We say that Problem A reduces to Problem B.

This implies that Problem A is "no harder than" Problem B. We can use this logic in reverse, which is the key to proving undecidability.

Suppose we already know that Problem A is undecidable (like $A_{TM}$). If we can show that Problem A reduces to a new Problem B, what does that tell us about B? If B were decidable (i.e., "easy"), then A would also have to be decidable, because we could solve A using the easy solution for B. This contradicts what we know about A. Therefore, B must also be undecidable.

This method allows us to build a chain of undecidable problems, all starting from our foundational result for $A_{TM}$.

The following video introduces this powerful idea.

Formalizing the Technique: Mapping Reducibility

To use reductions in formal proofs, we need a precise definition. The type of reduction we will focus on is called mapping reducibility.

First, we need the concept of a computable function.
A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ is computable if there is a Turing Machine that, for any input string $w$, halts with exactly $f(w)$ on its tape. Your experience building complex backends and data pipelines gives you a practical sense of this: a computable function is essentially any transformation for which you could write a program that is guaranteed to terminate and produce the output.

With that, we can define mapping reducibility.

Definition: Mapping Reducibility
A language $A$ is mapping reducible to a language $B$, written $A{\le }_{m}B$, if there exists a computable function $f$ such that for every string $w$:
$w\in A⟺f(w)\in B$
This function $f$ is called the reduction. It acts as a translator, converting any instance of problem $A$ into an equivalent instance of problem $B$.

To solidify these formal definitions, please review the following brief video and a short text excerpt.

The Undecidability Theorem

Now we can state the main theorem that makes mapping reducibility so useful.

Theorem: If $A{\le }_{m}B$ and $B$ is decidable, then $A$ is decidable.

Proof Idea:
To decide if $w\in A$, we can construct a decider for $A$ that:

1. Computes $f(w)$ using the computable function from the reduction.
2. Runs the decider for $B$ on the result, $f(w)$.
3. Accepts if the decider for $B$ accepts; rejects if it rejects.
   Since $w\in A⟺f(w)\in B$, this procedure correctly decides $A$.

The corollary is what we'll use to prove undecidability:

Corollary: If $A{\le }_{m}B$ and $A$ is undecidable, then $B$ is undecidable.

This is the contrapositive of the theorem. Proving that a language $B$ is undecidable using this method involves three steps:

1. Choose a language $A$ that you already know is undecidable (e.g., $A_{TM}$).
2. Construct a computable function $f$ that maps instances of $A$ to instances of $B$.
3. Prove that your function $f$ satisfies the condition: $w\in A⟺f(w)\in B$.

A common mistake is getting the direction wrong. You must reduce the known hard problem to the new problem you want to prove is hard.

Example: Proving that HALT_TM is Undecidable

Let's use mapping reducibility to prove that the language for the general Halting Problem is undecidable. We define it as:
$HAL{T}_{TM}=\{⟨M,w⟩\mid M\text{ is a TM and }M\text{ halts on input }w\}$
We will prove this is undecidable by showing that $A_{TM}{\le }_{m}HAL{T}_{TM}$.

1. Known Undecidable Language: $A_{TM}=\{⟨M,w⟩\mid M\text{ accepts }w\}$.

2. Target Language: $HAL{T}_{TM}$.

3. Construct the Reduction $f$:
   We need a computable function $f$ that takes an input $⟨M,w⟩$ for $A_{TM}$ and outputs an input $⟨M^{\prime },w^{\prime }⟩$ for $HAL{T}_{TM}$. The function $f$ is computed by a TM that performs the following steps:

   On input $⟨M,w⟩$:

   1. Construct the description of a new Turing Machine, $M^{\prime }$.
   2. The machine $M^{\prime }$ is defined as follows:
      On input $x$:
      a. Run $M$ on $x$.
      b. If $M$ accepts, then accept.
      c. If $M$ rejects, then enter an infinite loop.
   3. The function $f$ outputs $⟨M^{\prime },w⟩$. Notice we pass the string w through, but modify the machine M.

4. Prove Correctness:
   We must show that $⟨M,w⟩\in A_{TM}⟺f(⟨M,w⟩)=⟨M^{\prime },w⟩\in HAL{T}_{TM}$.

   • Forward direction ($\Rightarrow$): Assume $⟨M,w⟩\in A_{TM}$.

     • This means $M$ accepts $w$.
     • When we run $M^{\prime }$ on input $w$, it simulates $M$ on $w$. Since $M$ accepts, $M^{\prime }$ proceeds to its 'accept' step.
     • Therefore, $M^{\prime }$ accepts $w$, which means it halts.
     • So, $⟨M^{\prime },w⟩\in HAL{T}_{TM}$.

   • Backward direction ($\Leftarrow$): Assume $⟨M^{\prime },w⟩\in HAL{T}_{TM}$.

     • This means $M^{\prime }$ halts on input $w$.
     • Looking at the definition of $M^{\prime }$, the only way it can halt is by reaching its 'accept' step. It loops if $M$ rejects.
     • For $M^{\prime }$ to accept, the simulation of $M$ on $w$ must have accepted.
     • Therefore, $M$ accepts $w$.
     • So, $⟨M,w⟩\in A_{TM}$.

Since we have constructed a valid mapping reduction from the undecidable language $A_{TM}$ to $HAL{T}_{TM}$, we conclude that $HAL{T}_{TM}$ is also undecidable.

The following notes provide a clear, written example of this exact reduction.

Conclusion

Today we've added a powerful and efficient tool to our theoretical toolkit. Reducibility allows us to classify the difficulty of problems relative to each other. By formalizing this with mapping reducibility, we've developed a rigorous method for proving undecidability that avoids the complexities of diagonalization.

Key Takeaways:

• Reducibility is the technique of solving one problem by using a solution to another.
• If $A$ reduces to $B$, then $A$ is no harder than $B$. The contrapositive is key: if $A$ is undecidable, then $B$ must also be undecidable.
• A mapping reduction $A{\le }_{m}B$ is a computable function $f$ that transforms instances such that $w\in A⟺f(w)\in B$.
• To prove a language $B$ is undecidable, we can show $A_{TM}{\le }_{m}B$. This involves constructing the transformation function $f$ and proving it preserves the membership property.

Preview of the Next Lesson:
With this technique, we can now rapidly expand our catalog of undecidable problems. In the next lesson, we will apply reductions from $A_{TM}$ to prove that a variety of other fundamental questions about Turing Machines—such as whether a TM's language is regular, or whether two TMs accept the same language—are all undecidable. This will lead us to a sweeping generalization known as Rice's Theorem.