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.

A generic mapping reduction

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$ .

Theorem

Suppose $P \leq_m Q$ .

If $P$ is not decidable, then $Q$ is not decidable.
If $P$ is not semidecidable, then $Q$ is not semidecidable.

Proof:

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.
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:

Corollary

If $A_\mathrm{TM} \leq_m L$ then $L$ is not decidable.
If $\lnot A_\mathrm{TM} \leq_m L$ then $L$ is not semidecidable.

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

Example

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:

A_tm map-reduces to NEtm

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).

Example

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.

A_tm map-reduces to abba-fanatics

Example

There is no algorithm that can always tell us whether an arbitrary TM (code) could be reimplemented as a DFA. That is, the language

\mathit{DFA{-}like}\quad:=\quad\{\ \langle M\rangle\ |\ L(M) \mathrm{~is~regular}\ \}

is not decidable.

To show: $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$ 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.

A_tm map-reduces to DFA-like

Example

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}$

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.

A_tm map-reduces to DFA-like

Example

The language

\mathit{EQ}_\mathrm{TM} = \{\ \langle M_1,M_2\rangle\ |\ L(M_1) =L(M_2)\ \}

is not even semidecidable.

Proof. We will prove that $E_\mathrm{TM} \leq \mathit{EQ}_\mathrm{TM}$ .
Let $f$ be the function that turns the code $\langle M\rangle$ into the pair $\langle M,N\rangle$ where $N$ is a Turing Machine that rejects all strings.

(It’s not difficult to define a TM that rejects all strings; we just pick one and call it $N$ , and then define $f$ to be the function that returns its input $M$ paired with the fixed piece of code $N$ .)

If $\langle M\rangle\in E_\mathrm{TM}$ , then $L(M) = \emptyset = L(N)$ , so $\langle M,N\rangle\in\mathit{EQ}_\mathrm{TM}$ .
If $\langle M\rangle\not\in E_\mathrm{TM}$ , then $L(M) \not= \emptyset = L(N)$ , so $\langle M,N\rangle\not\in\mathit{EQ}_\mathrm{TM}$ .