CS 273: Help with Reductions

Reduction proofs are short and look simple. And your solutions to homework problems will be very similar to the examples in the book and lectures. However, reductions involve an unfamiliar type of abstraction. So most of you will find the homework problems unexpectedly hard. This is because the material is hard, not because you are more lost than the rest of the class.

This page tries to provide some additional help. We also strongly suggest going to head-banging and/or office hours. Also look at the page of additional reduction examples, intended to supplement the examples in Sipser. The old cs 375 reduction help page by Lenny Pitt might also be useful.

This page covers only the simpler types of reductions, which you are likely to encounter on homeworks or exams.

Is my language decidable or not?

Some problems ask you to determine whether some language L is decidable or not (and perhaps prove that your answer is correct).

Rice's theorem (Sipser solved exercise 5.28) states that any non-trivial property of Turing machines that depends only on the language that the Turing machine accepts is undecidable. For example, it's undecidable whether a Turing machine has a language that's non-empty, contains 17 elements, contains the string "UIUC", is infinite, and so forth.

Facts about the Turing machine's structure are decidable. For example, you can tell if the Turing machine has more than 15 states, has no transitions into its accept state, or the like. Such properties just require parsing the Turing machine's code and doing some straightforward check (e.g. counting the number of states listed).

Facts about a Turing machine's behavior may or may not be decidable, and it's not always easy to tell which. For example, it is decidable whether a Turing machine ever moves left. But it is not decidable whether a Turing ever moves left three times in a row. Normally, the decidable behaviors actually cripple the Turing machine, whereas the undecidable ones are cosmetic and still allow the machine to do the normal range of Turing machine tasks.

Basic template

To prove that a language L is undecidable, you will normally want to use a reduction from a language already known to be undecidable (e.g. ATM). A reduction proof will look something like:

Suppose that L were decidable. Let R be a Turing machine deciding L. We will now construct a Turing machine S that decides ATM.

S is constructed as follows:

But we know that ATM is undecidable. So S can't exist. Therefore we have a contradiction. So L must have been undecidable.

This is called reducing ATM to L. Sometimes you can write a shorter/simpler proof by replacing ATM with some other problem known to be undecidable. If so, remember that you may need to change the inputs to S, e.g. elements of the language EQTM are pairs of Turing machines. So a reduction from EQTM requires constructing a Turing machine S whose inputs are pairs <M1,M2> of two Turing machines.

If you aren't sure what problem to reduce to L, ATM is normally a good choice.

For simple examples of the basic idea, see Sipser's proof that HALTTM is undecidable (p. 188) and his proof that EQTM is undecidable (p. 192).

Turing machine language problems

In the simple examples above, S fed its inputs M and w more-or-less directly into the subroutine R. Many other problems require S to rewrite the code for M before feeding it to R. It is usually MUCH easier to imagine your Turing machines as written in Java or C. That is, S takes the source code for M (imagine a file of Java code) and writes a new file of source code for a new machine M'. Often, you can imagine S doing the rewrite by simple cut-and-paste, e.g. copying the input code for M and then adding a new main function and perhaps a few additional declarations.

The new Turing machine typically has w "hardcoded" into it. If you were writing the new machine's code in Java or C, you would write a local variable declaration and copy the input value of w into that declaration. E.g. if the input value was "Bob the Builder", the code for the new machine would contain a line like: w = "Bob the Builder". Therefore, we will typically use Mw as the name for the new Turing machine.

The Turing machine Mw is typically designed so it accepts one set of strings x (call the set X) if M accepts w, and a totally different set of strings x (call the set Y) if M doesn't accept w. One of these sets should have the property that R tests for and the other should not. For example, in the reductions for LUIUC and HALTEMPTYTM (in the additional examples page), Mw accepts all input strings x if M accepts w, and it accepts no input strings x if M doesn't accept w.

The code for Mw typically involves simulating M on w, plus some other tests on x that can clearly be computed in a predictable amount of time. For some reductions, we test x first, e.g.

For either of these two steps, you could also take the opposite action, e.g. reject all strings x that have property P. For examples of this pattern, see Sipser's reductions for ETM (p. 189) and REGULARTM (p. 191).

For some reductions, we simulate M on w first, before we test x. So the code for Mw looks like:

Examples of this pattern include L3 (on the additional examples page), and the proof of Rice's theorem (see Sipser's solved exercise 5.28 on p. 213).

Common problems writing these reductions

A common problem is to get confused about which values are input to which Turing machines. In the above proofs, the string w is an input to the machine S, i.e. the machine that decides ATM. The string x is an input to the Turing machine Mw. Look back through the proofs and check carefully where x occurs and where w occurs.

The input to the Turing machine R is usually the code for the machine Mw. You can imagine R as a Java or C program, which reads an ASCII file of source code for some other program. w and x are NOT inputs to R. The value of w is hardcoded into the code for Mw. The value of x is not specified. You can imagine that Mw will ask the user to input a value for x.

Since the value of x is not specified, R has to consider all possible values for the input x and figure out what Mw would do on each of these values. If R is testing a non-trivial property of Mw, you can imagine that it might be hard to figure out what it will do on all possible input strings x. Remember that R is only a hypothetical Turing machine whose existence will be contradicted at the end of the proof. That is, R can't really exist, because it's trying to do a task that's too hard.

Proving that a behavior is undecidable

Decidable behavior properties normally restrict the Turing machine's behavior in cosmetic ways, but still allow it to complete the standard range of Turing machine tasks. Such a problem involves a language L which is a set of all Turing machines with a specific behavior B. E.g. L = {<M> : M prints three 1's in a row on blank input} or L = {<M> : M has a state which is never entered on any input string}.

For this class of problems, reductions typically require modifying the input Turing machine code <M> to create code for a new Turing machine <M'> which does pretty much the same thing as M except that

Typical examples of this type of reduction are the proofs for L111 and Lx on the additional examples page In that example, we ensure that M' can never accidently print three ones in a row by replacing every instance of 1 in its code by a new character 1'.

Proving that a behavior is decidable

Decidable behavior properties normally restrict the Turing machine's behavior in a way that significantly cripples it. For an example of a decidable Turing machine behavior, consider the language L = {<M> : M never moves left on input "UIUC"}. L is decidable, because Turing machines that never move left are so crippled that they either halt very quickly, or not at all.

Specifically, if a Turing machine M never moves left, it reads through the whole input, then starts looking at blank tape cells. Once it is on the blank part of the tape, it can cycle through its set of states. But after |Q| moves, it has run out of distinct states and must be in a loop. So, if you watch M for four moves (the length of the string "UIUC") plus |Q|+1 moves, it has either halted or its in an infinite loop.

Therefore, to decide L, you run the input Turing machine for |Q|+5 moves. After that many moves, it has either

This algorithm is a decider (not just a recognizer) for L, because it definitely halts on any input Turing machine M.