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 , which is

On input where is a DFA then

- Simulate the DFA on input
- If the simulation accepts, accept. If the simulation rejects, reject.

Now, to prove that is decidable we need to give a reduction of it to , i.e. prove . To do this we need to make a Turing machine that, when given a pair where is an NFA and is the input string turns that into a pair where is a DFA and where accepts iff accepts . 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 where is an NFA:

- Convert to a DFA we’ll call
- Write the description of and onto the tape
- If is not an NFA we blank out the tape and halt

So for this function, is iff ? 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 iff that string is an element of .

What about a more complicated example? Consider the language . This is subtly different than , 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 but we can do this more easily by using a reduction. Recall last time when we stated that if and is undecidable then must be undecidable. In this case, we already know that is undecidable so if we can reduce to then we win. A reduction in this case means that we need to take a pair and map it to a pair such that iff . We’ll do this as follows

On input where is a Turing machine:

- Build a description for a new TM whose definition is On input then
- Simulate on
- If it accepts, accept, if it rejects loop

- Write the pair to the tape

We can see that the Turing machine will halt on a string iff the Turing machine will accept the string. This means that iff which is exactly what we needed. Thus, is undecidable.

What are some other languages we can prove undecidable this way? Well, let’s prove that is undecidable and, indeed, unrecognizable by showing that we can reduce to it. This means, again, that we need to turn a pair where doesn’t accept into a TM where 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 where is a Turing machine:

- Build a description for a new TM whose definition is On input then
- if accepts then accept else reject

- Write the description of to the tape

We can see that this is a Turing machine that, if accepts then the resulting will not be the empty language, but if rejects or loops then the language will be empty and thus an element of . This means that we have a proper reduction of to and thus cannot be recognizable and thus not decidable either.

Now, when I first thought about this problem I wanted to do a reduction of to as follows:

On input where is a Turing machine:

- Build a description for a new TM whose definition is On input then
- if accepts then reject else accept

- Write the description of to the tape

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