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. ATM). A reduction
proof will look something like:
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.
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).
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).
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.
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'.
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.
Basic template
Suppose that L were decidable. Let R be a Turing machine deciding L.
We will now construct a Turing machine S that decides ATM.
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.
Turing machine language problems
Common problems writing these reductions
Proving that a behavior is undecidable
Proving that a behavior is decidable