CSCI3390-Lecture 7: Undecidability Proofs;
Reductions
September 21,2018
1 Summary
• We prove the claims that all the problems about Turing machines listed in
the last lecture are undecidable.
• The main tool for proving this is to reduce the problem that we want to show
is undecidable to a problem we already know to be undecidable.
2 A collection of undecidable problems about Tur-
ing machines
Recall our list of problems.
2.1 Halting Problem, version 1
Input: A Turing machine M and a string w ∈ {0, 1}∗ .
Output: Yes if M eventually halts when started on input w, No otherwise.
2.2 Halting Problem, version 2
Input: A Turing machine M.
Output: Yes if M eventually halts regardless of the input string (i.e., M is free of
infinite loops), No otherwise (i.e., if M runs forever on some input).
1
2.3 Nonemptiness
Input: A Turing machine M.
Output: Yes if there is some w ∈ {0, 1}∗ accepted by M, no otherwise.
2.4 Finiteness.
Input: A Turing machine M.
Output: Yes if the set of strings accepted by M is finite, No if M accepts infinitely
many strings.
2.5 Equivalence
Input: Two Turing machines M, N .
Output: Yes M and N accept exactly the same strings, no otherwise.
2.6 Minimality
Input: A Turing machine M.
Output: Yes if M is the smallest Turing machine that recognizes the set of strings
it accepts, No if there is a smaller machine that recognizes the same language.
Here you have to say what exactly you mean by the size of a Turing machine.
One way to do this is to fix an encoding scheme, and use the length of the encoding
of M as the size of M.
3 Reductions
The main tool for proving a given problem Y is undecidable is to reduce another
problem X that we already know is undecidable to Y. In essence, this means that
we show that if we had an algorithm to decide Y , then we would have such an
algorithm for X (which we already know is not possible). We sometimes say that
we prove Y is undecidable by a ‘reduction from X’. Think of it this way—if we
had a Y subroutine, we could use it to write an X program.
The actual form these reductions take is to provide an algorithm for transform-
ing an instance u of problem X into an instance u0 of problem Y such that u0 is
a positive instance (a Yes instance) of Y if and only if u is a Yes instance for X.
2
Figure 1: Illustration of the reduction for the first version of the halting problem.
Every transition of M into the rejecting state is treated this way. The new machine
cycles endlessly in the new state q ∗ regardless of the tape symbols it encounters.
Then if we had an algorithm for Y we would obtain the following algorithm for
X: Take an input u, transform it to u0 and apply the algorithm for Y to u0 .1
Let’s see how this works in practice with our collection of problems from the
last section:
3.1 Halting Problem, version 1
We reduce LT M to this problem. Given a Turing machine M, we modify it to
produce a new Turing machine M0 as follows: We replace the rejecting state by a
new state q ∗ such that if M0 enters q ∗ , it runs forever. The modification is shown
in Figure 1.
The result is that M0 halts on an input string w if and only if M accepts w,
because if M rejects w, M0 would run forever. So if we had an algorithm for the
halting problem, we would get one for LT M . Given an input (M, w) for LT M , we
transform it to (M0 , w), and test if M0 halts on w. If it does, then M accepts w,
and if M0 does not halt on w, then M does not accept w.
3.2 Halting Problem, version 2
We reduce version 1 to this problem. Given M, w, we will show how to construct
a Turing machine M0 such that M0 halts on every input if and only if M halts
on w. Here is how M0 will work: initially, it erases its input, and then writes the
1
Students often get which way the reduction works backwards, and for good reason. To show
Y is undecidable, we reduce the known undecidable problem X to Y. But by this means, according
to a more common use of ‘reduce’, we are reducing the problem of proving Y undecidable to the
problem of proving X undecidable. So, yes, it’s confusing. You just have to think it through.
3
Figure 2: Illustration of the reduction for the second version of the halting prob-
lem, as well as the finiteness problem. The new machine begins by erasing its
input and then writing the string w (in this case 01) on the tape, and then running
M on w.
Figure 3: Illustration of the reduction for the nonemptiness problem. The new
machine first verifies that its input is identical to w (in this case 01), rejecting
otherwise. It then runs M on w.
input string w on its tape—this is hard-wired into the transitions of M0 . After this
initial phase, M0 returns to the start of the input and does what M does. This is
illustrated in Figure 2 for the case w = 01. Observe that in contrast to the previous
problem, the construction of M0 depends on the string w. So we can test if M
halts on w by testing whether M0 halts on every input.
3.3 Nonemptiness
We reduce LT M to this problem. Given M, w we construct a TM M0 that accepts
the string w if M accepts w, and accepts nothing at all if M does not accept w. So
to test if M accepts w, we construct M0 and test it for nonemptiness. M0 works
as follows: In an initial scan, it checks to see if its input is equal to w, and if it is
not, M0 rejects the input. Otherwise, M0 returns to the left end of the tape, and
simulates M. Thus M0 is a Yes instance of the nonemptiness problem if and only
if M, w is a Yes instance of LT M . The construction is illustrated in Figure 3 for
the case w = 01.
4
Figure 4: The machine M∅ used in the reduction of the equivalence problem to
the emptiness problem. This machine accepts no string over the alphabet {0, 1},
thus it recognizes the empty language.
3.4 Finiteness
Again, we reduce from LT M . We use exactly the same construction as in version
2 of the halting problem: Given M and w, we construct a new TM M0 that erases
its input, writes w on the tape, and then simulates M on w. Thus M0 accepts
an infinite set of strings (in fact every string) if M accepts w, and a finite set of
strings (the empty set) if M does not accept w.
3.5 Equivalence
Reduction from nonemptiness (or, rather, from its complement emptiness). If we
could test for equivalence of two Turing machines, we could test whether a given
Turing machine M is equivalent to the TM M∅ shown in Figure 4, which recog-
nizes the empty language. That is, we transform an instance M of the emptiness
problem into the instance (M, M∅ ) of the equivalence problem. Thus if we could
decide whether two TMs are equivalent, we could decide whether a given TM
recognizes the empty language.
4 Reductions formally
Remember that in a more formal setting, decision problems are languages over
some input alphabet. So, formally, a reduction of a (known undecidable) problem
X to another problem Y is a reduction of a an undecidable language L ⊆ Σ∗1 to
L0 ⊆ Σ∗2 . The reduction itself is a function
f : Σ∗1 → Σ∗2
with the property that w ∈ L if and only if f (w) ∈ L0 . One additional, crucial
requirement is that f be computable. There has to be an algorithm for computing
5
f ; that is, there is some T M N such that f = fN . We adopt our usual practice
of assuming the Church-Turing thesis, and simply describe the algorithm, rather
than the Turing machine N .
For instance, the reduction for version 2 of the halting problem is officially a
function that takes a string < M, w >∈ {0, 1}∗ and produces the string < M0 >∈
{0, 1}∗ .
5 A different kind of reducibility
The reductions described above are called mapping reductions. There is a more
general kind of reduction, which we can also use to prove undecidability. Let us
describe another proof that the first version of the halting problem is undecidable,
using the fact that LT M is decidable. Assuming we have an algorithm A for the
halting problem, here is our algorithm for LT M : Given M, w, use A to determine
if M halts on w. If the answer is ‘no’, then reject: we know that M does not
accept w. If the answer is ‘yes’, then we know that M either accepts or rejects w.
So now we can just run M on w, assured that we will eventually get a result, and
accept or reject accordingly. Thus we are able to decide in any case whether M
accepts w. Of course we already know that we can’t decide this, so the algorithm
A does not exist.
6 Some decidable problems
Consider the following two problems:
• Input: a TM M and an input word w over the input alphabet of M. Output:
Yes, if M halts within the first million steps when run on w; no otherwise.
• Input: a TM M and a word w over the input alphabet of M. Output: Yes,
if M visits fewer than 20 tape cells when run on w; no otherwise.
The first of these problems is obviously decidable: The algorithm to decide it
is to simply simulate M on w, counting steps, until either M halts, or one million
steps have been performed and the machine is still going.
While this is less obvious, the second problem is also decidable. Consider
the following algorithm, which will tell us if the reading head ever moves more
than 20 tape cells from the starting point. The total space we will allow the head
6
to cover consists of 41 cells. If Γ is the tape alphabet, then there are |Γ|41 ways
we can write symbols into those 41 cells. There are |Q| possible states, and 41
possible positions for the reading head. All in all, this makes
41 · |Q| · |Γ|41
allowable configurations that M can be in and still remain within the allowed
region. So our algorithm is this: Simulate M on w for 1+41·|Q|·|Γ|41 steps. If the
reading head leaves the allowed region during this simulation, then then answer
is no. If the reading head does not leave the region, then some configuration must
have occurred twice: That is, from some configuration c, after running for some
positive number of steps, the machine re-enters c. This means that it will continue
to repeat the same sequence of configurations, over and over again, and will never
leave the allowed region. (It also means we know the machine will never halt.)
The original problem asks whether the machine ever visits 20 or more cells. So far,
we have only determined whether or not it strays out of the allowed 41-cell region.
Of course, if it does, then we know it visited more than 20 cells. If it doesn’t, we
can count the exact number of distinct cells visited during the simulation and get
the answer.
