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.

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

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.

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. A_{TM}). 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 AThis is called reducing A_{TM}.S is constructed as follows:

- Input is <M,w>, where M is the code for a Turing Machine and w is a string.
- [Pseudocode explaining how S decides whether M accepts w, using R as a subroutine.]
But we know that A

_{TM}is undecidable. So S can't exist. Therefore we have a contradiction. So L must have been undecidable.

If you aren't sure what problem to reduce to L, A_{TM} is
normally a good choice.

For simple examples of the basic idea, see
Sipser's proof that HALT_{TM} is undecidable (p. 188)
and his proof that EQ_{TM} is undecidable (p. 192).

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 M_{w} as the name for the
new Turing machine.

The Turing machine M_{w} 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 L_{UIUC} and
HALTEMPTY_{TM}
(in the
additional examples page),
M_{w} 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 M_{w} 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.

- input is a string x.
- If x has some easily-tested property P, accept.
- Simulate M on w and accept if M accepts w.

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
E_{TM} (p. 189) and REGULAR_{TM} (p. 191).

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

- Simulate M on w.
- If M rejects, reject.
- Otherwise, accept exactly when x has some easily-tested property P.

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

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 A_{TM}. The string x is an input to
the Turing machine M_{w}. 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 M_{w}. 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 M_{w}.
The value of x is not specified. You can imagine that M_{w}
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 M_{w} would do on each of these values.
If R is testing a non-trivial property of M_{w}, 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.

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

- When M would have halted, M' first does behavior B before halting, and
- M' never accidently does behavior B while it's computing.

Typical examples of this type of reduction are the proofs for
L_{111} and L_{x}
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'.

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

- moved left (in which case you reject), or
- has halted or gone into an infinite loop without ever moving left (in which case you accept).

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