# Lecture: More on Reductions

Let’s go back and redo our results about regular languages except in terms of reductions. We’ll try to be very formal for this section. To start with, we recall the machine that decides the language $A_{DFA} = \{(M,w) | M \text{ accepts the string } w\}$, which is

On input $(M,w)$ where $M$ is a DFA then

1. Simulate the DFA $M$ on input $w$
2. If the simulation accepts, accept. If the simulation rejects, reject.

Now, to prove that $A_{NFA}$ is decidable we need to give a reduction of it to $A_{DFA}$, i.e. prove $A_{NFA} \le_m A_{DFA}$. To do this we need to make a Turing machine that, when given a pair $(N,w)$ where $N$ is an NFA and $w$ is the input string turns that into a pair $(M,w)$ where $M$ is a DFA and where $M$ accepts $w$ iff $N$ accepts $w$. We already know this is possible, though, because the power-set construction for turning an NFA into a DFA is definitely a computable function. So our reduction will will look

On input $(N,w)$ where $N$ is an NFA:

1. Convert $N$ to a DFA we’ll call $M$
2. Write the description of $M$ and $w$ onto the tape
3. If $N$ is not an NFA we blank out the tape and halt

So for this function, is $(N,w) \in A_{NFA}$ iff $(M,w) \in A_{NFA}$? Yes! We know that because the powerset construction creates a DFA that decides the exact same language as the original NFA. Just for being truly rigorous we’ve defined what happens if we aren’t given an NFA. We just need to do this to make sure that our computable function sends a string into $A_{DFA}$ iff that string is an element of $A_{NFA}$.

What about a more complicated example? Consider the language $H = \{(M,w) | M \text{ halts on the string } w\}$. This is subtly different than $A_{TM}$, since it’s not asking whether the Turing machine accepts the string but rather if the Turing machine either accepts or rejects in finite time. Is this language decidable? We could do a very similar argument to our previous one about $A_{TM}$ but we can do this more easily by using a reduction. Recall last time when we stated that if $A \le_m B$ and $A$ is undecidable then $B$ must be undecidable. In this case, we already know that $A_{TM}$ is undecidable so if we can reduce $A_{TM}$ to $H$ then we win. A reduction in this case means that we need to take a pair $(M,w)$ and map it to a pair $(N,w)$ such that $(N,w) \in H$ iff $(M,w) \in A_{TM}$. We’ll do this as follows

On input $(M,w)$ where $M$ is a Turing machine:

1. Build a description for a new TM $R$ whose definition is On input $s$ then
1. Simulate $M$ on $s$
2. If it accepts, accept, if it rejects loop
2. Write the pair $(R,w)$ to the tape

We can see that the Turing machine $R$ will halt on a string iff the Turing machine $M$ will accept the string. This means that $(R,w) \in H$ iff $(M,w) \in A_{TM}$ which is exactly what we needed. Thus, $H$ is undecidable.

What are some other languages we can prove undecidable this way? Well, let’s prove that $E_{TM} = \{ M | L(M) = \emptyset \}$ is undecidable and, indeed, unrecognizable by showing that we can reduce $\overline{A_{TM}}$ to it. This means, again, that we need to turn a pair $(M,w)$ where $M$ doesn’t accept $w$ into a TM $N$ where $L(N)$ is empty. The way we’ll do this is much like our previous example, where we build a new Turing machine that has the property we want and pass that on as input. So our computable reduction will be

On input $(M,w)$ where $M$ is a Turing machine:

1. Build a description for a new TM $R$ whose definition is On input $s$ then
1. if $M$ accepts $w$ then accept else reject
2. Write the description of $R$ to the tape

We can see that this is a Turing machine that, if $M$ accepts $w$ then the resulting $R$ will not be the empty language, but if $M$ rejects $w$ or loops then the language will be empty and thus an element of $E_{TM}$. This means that we have a proper reduction of $\overline{A_{TM}}$ to $E_{TM}$ and thus $E_{TM}$ cannot be recognizable and thus not decidable either.

Now, when I first thought about this problem I wanted to do a reduction of $A_{TM}$ to $E_{TM}$ as follows:

On input $(M,w)$ where $M$ is a Turing machine:

1. Build a description for a new TM $R$ whose definition is On input $s$ then
1. if $M$ accepts $w$ then reject else accept
2. Write the description of $R$ to the tape

and that certainly seemed reasonable at first, because if $(M,w)$ is in $A_{TM}$ then the language for $R$ will be empty. Ah, but this is where the iff part of things is important because while things are all well and good if $M$ actually rejects the string $w$, iff $M$ loops on $w$ then $L(R)$ is going to be the empty language even though $M$ didn’t accept the string. Oops!