6.21 Mapping Reductions

The goal of a reduction proof is to bootstrap what we already know, arguing that since \(X\) is not decidable (or not semidecidable), \(Y\) can’t be decidable (or semidecidable) either. One particularly convenient form of reduction is mapping reduction (also known as many-one reduction).

We say that \(P \leq_m Q\) if there is a computable function \(f:\Sigma^* \to \Sigma^*\) such that \[ x\in P\quad\leftrightarrow\quad f(x)\in Q \] for all \(x\in \Sigma^*\).

The intuition is this: we have a language \(P\) and a string \(x\) which may or may not be in \(P\).

![Is x in P?

The trick is that instead of answering “is \(x\) in \(P\)?” directly, we can ask the question “is \(f(x)\) in \(Q\)?” for some computable function \(f\) chosen so that the answers to the two questions are the same.

As soon as we find a computable function \(f\) with this property, we have a mapping reduction \(P \leq_m Q\); any question about membership in \(P\) can be turned into a question about membership in \(Q\), and so determining membership in \(P\) cannot be any harder than determining membership in \(Q\).

Suppose \(P \leq_m Q\). > >1. If \(P\) is not decidable, then \(Q\) is not decidable. >2. If \(P\) is not semidecidable, then \(Q\) is not semidecidable. > >Proof: > >1. Suppose \(x\in P\) iff \(f(x)\in Q\). If \(f\) is a function that a TM can compute, then given any algorithm decide_Q, we can write a decider for \(P\) that uses the following algorithm: > > > def decide_P(x): > return decide_Q(f(x)) > > > It follows that if \(Q\) is decidable then so is \(P\). >
>By the contrapositive, if \(P\) is not decidable, then \(Q\) is not decidable. > >2. Suppose \(x\in P\) iff \(f(x)\in Q\). If \(f\) is a function that a TM can compute, then given any algorithm semidecide_Q, we can write a semidecider for \(P\) that uses the following algorithm: > > > def semidecide_P(x): > return semidecide_Q(f(x)) > > > It follows that if \(Q\) is semidecidable then so is \(P\). >
> By the contrapositive, if \(P\) is not semidecidable, then \(Q\) is not semidecidable.

We have already seen that \[ A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ w\in L(M)\ \} \] is not decidable, and that \[ \lnot A_\mathrm{TM} = \{\ \langle M, w\rangle\ |\ w\not\in L(M)\ \} \] is not semidecidable, which gives us:

Proving Mapping Reductions

What does a proof look like?

A typical mapping reduction proof that \(L_1\leq_m L_2\) goes as follows:

[Define a function \(f\) mapping strings to strings.]
[If nonobvious, explain why \(f\) is computable.]
[Show that if \(x\in L_1\) then \(f(x) \in L_2\).]
[Show that if \(x\not\in L_1\) then \(f(x)\not\in L_2\).]
Therefore \(x\in L_1\) iff \(f(x)\in L_2\), so \(L_1\) map-reduces to \(L_2\).
QED.

Why is this useful?

A successful proof (exhibiting a function \(f\) that maps strings in \(L_1\) to strings in \(L_2\) and maps strings not in \(L_1\) to strings not in \(L_2\)) guarantees that \(L_1 \leq L_2\) both in terms of decidability (if \(L_1\) is not decidable then \(L_2\) is not decidable) and in terms of semidecidability (if \(L_1\) is not semidecidable then \(L_2\) is not semidecidable).

This means that if we do a mapping-reduction proof where \(L_1\) is a language like \(A_\mathrm{TM}\) that we already know is not decidable, then just finding a suitable function \(f\) guarantees that \(L_2\) is not decidable.

And if we do a mapping-reduction proof where \(L_1\) is a language like \(\lnot A_\mathrm{TM}\) that we already know is not semidecidable, then just finding a suitable function \(f\) guarantees that \(L_2\) is not semidecidable.

Examples

We previously showed that the language >\[ >\mathit{NE}_\mathrm{TM} = \{\ \langle M\rangle\ |\ L(M) \not= \emptyset\ \} >\] >of Turing Machines (programs) that accept at least one string is semidecidable. > >Let \(f\) be the function that takes \(\langle M,w\rangle\) and returns (the code for) a Turing Machine \(M'\) that ignores its input, and instead simulates \(M\) running on the specific input \(w\). > Clearly \(f\) is computable. (Given the code for \(M\) and a specific string \(w\), we can produce a slightly longer piece of code that ignores its input and runs the code \(M\) on the specific string \(w\).). Note that \(f\) does not run \(M\) on \(w\)! The input of \(f\) is a piece of code and a string; the output is a slightly longer piece of code. > >- If \(\langle M,w\rangle\in A_\mathrm{TM}\), then \(L(M') = \Sigma^*\), and so \(M' \in \mathit{NE}_\mathrm{TM}\). If \(M\) accepts \(w\), a Turing Machine that ignores its input and runs \(M\) on \(w\) will accept not matter what input we provide. > >- If \(\langle M,w\rangle\not\in A_\mathrm{TM}\), then \(L(M') = \emptyset\), and so \(M' \not\in \mathit{NE}_\mathrm{TM}\). If \(M\) does not accept \(w\), a Turing Machine that ignores its input and runs \(M\) on \(w\) will not accept any input we provide. > >So \(\langle M,w\rangle\in A_\mathrm{TM}\) if and only if \(f(\langle M,w\rangle) = M'\in \mathit{NE}_\mathrm{TM}\) . > >This proves \(A_\mathrm{TM} \leq_m \mathit{NE}_\mathrm{TM}\) and so \(\mathit{NE}_\mathrm{TM}\) is not decidable. > >— > >Intuitively, the above proof shows that \(\mathit{NE}_\mathrm{TM}\) is not decidable because it is “harder than” the undecidable language \(A_\mathrm{TM}\), as shown by the following mapping reduction: > > which shows that if we had a decider for \(\mathit{NE}_\mathrm{TM}\) (on the right) then we could combine it with this mapping function \(f\) to build a decider for \(A_\mathrm{TM}\) (on the left).

There is no algorithm that can always tell us whether an arbitrary TM (code) accepts the string abba and nothing else. That is, the language >\[ >\mathtt{abba}{-}\mathit{fanatics}\quad:=\quad\{\ \langle M\rangle\ |\ L(M) = \{\mathtt{abba}\}\ \} >\] >is not decidable. > >— >To show: \(A_\mathrm{TM} \leq_m \mathtt{abba}{-}\mathit{fanatics}\) > >Let \(f\) be the function that takes \(\langle M,w\rangle\) and returns (the code for!) a Turing Machine \(M'\) that accepts its input if the input is abba and \(M\) accepts \(w\). > >- If \(\langle M,w\rangle\in A_\mathrm{TM}\), then \(L(M') = \{\mathtt{abba}\}\). >- If \(\langle M,w\rangle\not\in A_\mathrm{TM}\), then \(L(M') = \emptyset \not= \{\mathtt{abba}\}\). > >So \(\langle M,w\rangle\in A_\mathrm{TM}\) if and only if \(f(\langle M,w\rangle) = M'\in \mathtt{abba}{-}\mathit{fanatics}\) , as required. >

Let \(f\) be the function that takes \(\langle M,w\rangle\) and returns (the code for!) a Turing Machine \(M'\) that accepts its input if the input has the form \(\mathtt{0}^n\mathtt{1}^n\) for some \(n\geq 0\) or if \(M\) accepts \(w\). > >- If \(\langle M,w\rangle\in A_\mathrm{TM}\), then \(L(M') = \Sigma^{*}\) (which is regular). >- If \(\langle M,w\rangle\not\in A_\mathrm{TM}\), then \(L(M') = \{\ \ 0^n1^n\ |\ n\geq 0\ \}\) (non-regular). > So \(\langle M,w\rangle\in A_\mathrm{TM}\) if and only if \(f(\langle M,w\rangle) = M'\in \mathit{DFA{-}like}\), as required. >

In fact, the language >\[ >\mathit{DFA{-}like}\quad:=\quad\{\ \langle M\rangle\ |\ L(M) \mathrm{~is~regular}\ \} >\] >of TMs equivalent to some DFA is not even semidecidable. > >— > >To show: \(\lnot A_\mathrm{TM} \leq_m \mathit{DFA{-}like}\) > >Let \(f\) be the function that takes \(\langle M,w\rangle\) and returns (the code for!) a Turing Machine \(M'\) that accepts its input if the input has the form \(\mathtt{0}^n\mathtt{1}^n\) for some \(n\geq 0\) and \(M\) accepts \(w\). > >- If \(\langle M,w\rangle\in \lnot A_\mathrm{TM}\), then \(L(M') = \emptyset\) (which is regular). >- If \(\langle M,w\rangle\not\in \lnot A_\mathrm{TM}\), then \(L(M') = \{\ \ 0^n1^n\ |\ n\geq 0\ \}\) (which is not regular). > >So \(\langle M,w\rangle\in A_\mathrm{TM}\) if and only if \(f(\langle M,w\rangle) = M'\in \mathit{DFA{-}like}\), as required. > Since \(\mathit{DFA{-}like}\) is not semidecidable, it is also not decidable. Had we done this reduction first, we could have skipped the previous Example. >

Previous: 6.20 Reductions

Next: Rice’s Theorem