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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s