Reductions

Now that we have seen one example of a language that is undecidable we are going to use that initial language to prove that many other languages are undecidable.

The first technique that we are going to use to do this is call reducibility. We say that a language A is reducible to a language B if we can use a decider for the language B to help us decide the language A.

More important is the converse of this relationship: if language A is known to be undecidable and A reduces to B, then we can conclude that B must be undecidable.

How reductions are useful

Let's talk first about the concept of a reduction. We say that one problem is reducible to another if the solution to the second problem provides a key step in solving the first problem.

To see how this works, let's engage is a short counter-factual. We already know that A_TM is undecidable, but let's pretend for a moment that we did not know this and someone gave us the job of building a decider for A_TM. It turns out that the key step in solving A_TM is the problem of determining whether or not a Turing machine halts on a given input. For that, suppose we have solved the halting problem for Turing machines, and that we have a decider H for the halting problem. Here is how we would build a decider for A_TM.

On input <M,w>:

1. Run H on the pair <M,w>.
2. If H rejects, stop and reject.
3. Simulate M running on w and accept if M does. Otherwise, reject.

This is an example of using a reduction to solve a problem. It's a bogus example, because neither A_TM nor the halting problem is decidable, but the example does demonstrate how often the key step in solving one problem is to reduce it to another problem.

The language E_TM

As our first example of this technique at work we will use the undecidability of A_TM to prove that E_TM is undecidable. E_TM is the problem of deciding where or not a given Turing machine accepts no inputs.

Our first challenge is finding a way to reduce A_TM to E_TM. To do this, we imagine creating a Turing machine program that could decide A_TM. That program has the following structure:

On input <M>, w where <M> is a description of a Turing machine:

1. Do ??? to the input
2. Run the decider for E_TM on ??
3. Use the result that the decider returns to answer the original question

This shows in outline form what we have to do. We are trying to build a decider for A_TM, so the machine that we build has to accept the same inputs that any A_TM decider would accept. To get A_TM to reduce to E_TM we have to have a step in our machine where we run the decider for E_TM. Finally, we have to somehow use the result that that decider returns to answer the original question: will <M> accept w?

One thing that we have to do to make this all work is to do something in step 1 to prepare an input that we can pass along to the E_TM decider. The E_TM decider will be expecting to receive a description of a machine as its input.

Our first attempt to get this to work is this.

On input <M>, w where <M> is a description of a Turing machine:

1. Run the decider for E_TM on <M>
2. If that decider accepts, it means that M accepts no inputs, so it certainly won't accept w. In this case we can reject the original input.
3. If that decider rejects, it simply means that M accepts some input, but this does not help us to decider whether or not M will accept w. We are now stuck.

Here is a better solution: we use <M> and w together to build a second machine, N, that we then pass to the decider for E_TM. N is set up so that the answer that E_TM returns is more helpful to us.

Here is a description of the intermediate machine N:

On input x:

1. If x ≠ w, stop and reject.
2. Simulate w running on M, and accept if M does.

We now use the intermediate machine to make the reduction work.

On input <M>, w where <M> is a description of a Turing machine:

1. Construct the machine N described above from <M> and w.
2. Run the decider for E_TM on <N>
3. If that decider accepts, it means that N accepts no inputs, including w. This tells us that M does not accept w. Stop and reject
4. If that decider rejects, it means the N accepts at least one input. The only input that N could possibly accept is w, and N accepts w because M does. Stop and accept.

Now that we constructed a valid reduction from A_TM to E_TM we can prove that E_TM is undecidable. We know already that A_TM is undecidable, so the machine we constructed above can not possibly work. The only conclusion we can draw from that observation is that there must not exist a decider for E_TM, since we have just shown how to use a decider for E_TM to build a decider for A_TM.

The language EQ_TM

The general equality problem, EQ, is the problem of determining whether or not two machines accepts the same languages. The Turing machine variant, EQ_TM, is the problem of determining whether or not two Turing machines accept the same language.

We show that EQ_TM is undecidable by reducing E_TM to EQ_TM:

On input <M>

1. Construct the pair <M,N>, where N is a Turing machine that rejects all of its inputs.
2. Run the decider for EQ_TM on the input <M,N>.
3. If it accepts, that means that M accepts the same language as the machine that accepts the empty language. This means that M accepts nothing. Stop and accept.
4. If the decider rejects, it means that M does not accept the empty language, so M accepts something. Stop and reject.

Mapping reducibility

One feature that reduction proofs all have in common is that in the reduction step we have to map the original inputs for one problem into inputs for an intermediate machine. We can abstract this process somewhat by writing out the generic outline for a reduction from one language A to another language B:

On input x, where is a potential member of A:

1. Compute f(x)
2. Run the decider for B on f(x)
3. If B accepts f(x), we conclude that x must have been in A, so we stop and accept.
4. If B rejects f(x), we conclude that x must not have been in A, so we stop and reject.

The function f that we have introduced here abstracts away the process of mapping A to B.

To make all of this work, and to give us a new framework for doing reductions, we introduce two important definitions.

Definition A function f(x) is a computable function if there exists some Turing machine, which, when started with x on its tape, stops running with f(x) written on its tape.

Definition A language A is mapping reducible to a language B (written A ≤_m B) if there exists some computable function f such that x ∈ A if and only if f(x) ∈ B.

The following two key theorems show the usefulness of this new framework.

Theorem If A ≤_m B and B is decidable, then A is decidable.

Proof Here is a decider for A:

On input x, where is a potential member of A:

1. Compute f(x)
2. Run the decider for B on f(x)
3. Since A ≤_m B, we have that f(x) ∈ B if and only if x ∈ A. If the decider for B accepted f(x), it means that f(x) ∈ B, and thus x ∈ A. We stop and accept.
4. Likewise, if the decider for B rejects f(x) it means that f(x) is not in B and thus x is not in A. We stop and reject.

Theorem If A ≤_m B and A is undecidable, then B is undecidable.

Proof We assume, by way of contradiction, that B is decidable. The proof of the last theorem then allows us to conclude that A must be decidable. This is a contradiction, so B must have been undecidable all along.

An example

As an example of the application of some of these ideas I will solve problem 20 from the end of chapter five.

This problem says "Prove that there exists an undecidable subset of {1}^*."

Not surprisingly, we can prove this via a mapping reduction from A_TM. All we have to do is to figure out how to map members of A_TM to members of {1}^*. The trick in this case is a common trick in the theory of computation, an encoding trick. Members of A_TM take the form <M>,w. These are strings in some alphabet that encode the structure of the machine M and the input string w. As computer scientists, we know that all strings can be written as sequences of bits in some character encoding scheme. We also know that sequences of bits can be interpreted as integers in binary notation. The final trick is to take the associated integer and recode it in an alternative notation, unary notation. In unary notation the integer n is represented as a sequence of n 1s.

In summary:

<M>, w ⇒ string of characters ⇒ bit sequence ⇒ integer in binary ⇒ integer in unary

Here now is the mapping f that we will use for our reduction.

On input x:

1. Recode x in binary.
2. Interpret the binary sequence as an integer, n.
3. Recode n in unary and finish with that recoding written on the tape.

Our undecidable subset of {1}^* is the image of A_TM under the mapping f.