Reductions in Computability Theory
Prakash Panangaden
22nd March 2021
The concept of reduction is central to computability and complexity theory.
The phrase “P reduces to Q” is often used in a confusing way. In this note
I will clarify how it is used and explain the difference between two different
notions of reduction: many-one reduction and Turing reduction.
Intuitively “P reduces to Q” means that if you can solve problem Q then
you can solve problem P . A reduction is an explicit proof of this implication.
The notation is P ≤ Q. The phrasing is, in my opinion confusing, whereas
the notation conveys a clear message. If P ≤ Q then Q is more difficult than
P , this is what the notation suggests. If Q is more difficult than P then if we
show P ≤ Q and P is something that we know is undecidable then we know
that Q must be undecidable. This is usually how we use reductions.
We start with HP ≤ Q where HP stands for the halting problem and thus
show Q is undecidable. Thus we expand out stock of undecidable problems.
When we know that Q is undecidable we can do another reduction Q ≤ R
and now we know that the problem R is undecidable. Thus the relation ≤
is transitive: we can chain reductions together.
It is time for some precise definitions. We assume that we are working with
some fixed alphabet Σ and we are considering strings in Σ∗. We assume
that all the problems that we consider are language membership problems.
Recall that a language is just a subset of Σ∗. This is not a restriction:
all computational problems can be recast easily as language membership
problems. Now we can talk about a language A being reduced to B: this
means that if you can solve the problem “is the word w in B?” you can
solve the problem “is the word x in A?”
Definition 1. A language A is said to be mapping reducible to1 B,
1Many, in fact, most books call this “many-one” reducibility.
1
written A ≤m B, if there is a total computable function f : Σ∗ −→ Σ∗ such
that x ∈ A if and only if f(x) ∈ B. The function f is called the reduction.
Even though there is an “if and only if” in the definition it is not a symmetric
concept. If we have such a reduction and we have an algorithm to decide
membership in B we can clearly use it to decide membership in A. It is
crucial that we have the “if and only if” for this to work correctly. Note,
however, that if we had an algorithm to decide membership in A it cannot
be used to decide membership in B. Why not? Because there is no reason
to assume that f is a surjection. So given a word w for which we wish to
answer the question “is w in B?” we would need to find an x such that
f(x) = w: there is no reason to think that we can find such an x.
The following theorem is obvious from the discussion above.
Theorem 2. If A ≤m B and B is decidable then A is decidable. Conversely,
if A is undecidable then B must be undecidable.
In fact mapping reduction is a very strong relation and can be used to
establish more.
Theorem 3. If A ≤m B and B is CE (or Turing recognizable) then so is
A. If A is not CE then neither is B.
Proof . Suppose that B is CE so there is an algorithm isinB which on an
input x will halt and say “true” if x is in B and may loop forever if x is not
in B. Now we define an algorithm isinA as follows:
1. Read input x
2. Apply f to x to produce y
3. Run isinB on y
4. Output whatever the line 3 produces
Line 2 must terminate because f is total. If x is in A and the reduction
is correct then f(x) = y ∈ B. Since we have an algorithm isinB that is
guaranteed to terminate and say “true” if its input is in B we know that
isinA terminates and says “true” if x ∈ A. If x is not in A, then f(x) will
not be in B and line 3 may run forever. Thus A is CE. If A is not CE, then
B cannot be CE by contraposing what we just proved.
Recall that a set is called co-CE if its complement is CE. Thus the non-
halting set
HTM
def
= {〈M,x〉|M(x) ↑}
2
is a typical example of a co-CE set. We can use mapping reductions to
show that some sets are not CE by showing reductions from this set. First
an important observation. It says that mapping reduction respects comple-
mentation. It is obvious from the definition of ≤m.
Observation 4. If A ≤m B then A ≤m B.
Now we can state the following corollary.
Corollary 5. If A ≤m B and A is CE but not decidable then B is not
co-CE.
Proof . If B were co-CE then B would be CE and the mapping reduction
could be rewritten as A ≤m B so we would have that A is CE. But if A is
CE and A is also CE then A is decidable. This contradicts the assumption
that A is not decidable.
Now for an example. We define the language of (encodings of) Turing ma-
chines that accept nothing:
EMPTM
def
= {〈M〉|L(M) = ∅}.
Intuitively, this should be clearly undecidable. We will prove this by showing
ATM ≤m EMPTM . We need to define a reduction function f : Σ∗ −→
Σ∗ which is total and computable. We assume that Σ consists of all the
characters that one has in a typical programming language. The problem
we are trying to solve is: given 〈M,w〉, the encoding of a Turing machine M
and a word w, accept if and only if M accepts w. Our reduction function has
to work with any string, not just strings that are encodings of acceptance
problems. We settle this by mapping any string that is not of the right form
to the string “fubar.” This string is certainly not part of EMPTM so we are
fine. Now, we define a new TM M ′:
Input x
Simulate M on w
If M accepts w accept x
Now clearly if M accepts w, M ′ will accept every input and if M does not
accept w then M ′ will not accept anything. Thus
w ∈ L(M)⇔ L(M ′) 6= ∅.
We do not ever run M ′. We write the code of M ′ and feed 〈M ′〉 to the
supposed decision algorithm for EMPTM . Thus if we could decide EMPTM
3
we could decide ATM which we know is impossible. Our function f reads
its input, if it is in the right format it will output the code of M ′, if it is in
the wrong format it will output “fubar”; this is a total computable string
to string function. In subsequent discussions I will not mention what to do
if the strings are not in the right format to constitute an instance of the
decision problem of interest.
Of course, this also shows that EMPTM is undecidable. However, it is
impossible to find a mapping reduction from ATM to EMPTM . If we could
do that we would have also shown that ATM ≤m EMPTM . But we can
easily see by dovetailing that EMPTM is CE. Then we would conclude that
ATM is CE, hence ATM is co-CE; but we known that ATM is CE. These
two facts together imply that ATM is decidable, a contradiction.
An easy exercise at this point is to show EMPTM ≤m ATM ; this also shows
that EMPTM is CE and hence that EMPTM is co-CE. A slight modification
of your solution to this exercise will show that EMPTM ≤m ATM .
Here is the solution to EMPTM ≤m ATM . We take the input 〈M〉 given
as an instance of the problem 〈M〉 ∈ EMPTM . We construct the code of
the following Turing machine M ′:
Input x (ignored)
Dovetail M on all words
If it accepts any word accept x
Now clearly M ′ does not accept the empty word if and only L(M) = ∅.
What we definitely do not have is EMPTM ≤m ATM . I will now describe
a more liberal notion of reduction called Turing reduction.
Definition 6. Let P be a language (or decision problem). We say that M
is a Turing machine with oracle P , written MP if M is an ordinary Turing
machine which can at any time obtain, in one step, a definite answer to the
question w ∈ P for any word w.
An example is a Turing machine which can consult an “oracle” and find the
answer to the halting problem for any instance of HP. Now suppose that I
have a TM equipped with an oracle for ATM . With such a TM I can solve
the emptiness problem. Here is how: given 〈M〉, we define a new machine
called N which works as follows:
Input x (ignored)
Dovetail M on all words
4
If M accepts any word accept x
We then ask our oracle if 〈N, ε〉 ∈ ATM . If the oracle says “no” accept
〈M〉 else reject. If L(M) = ∅ then N does not accept ε. Thus by flipping
the oracle’s answer we can answer the emptiness problem for the original
machine. This shows that EMPTM ∈ TMATM .
Definition 7. We say that A Turing reduces to B, written A ≤T B, if a
Turing machine with an oracle for B can answer membership queries for A.
What we have shown above is EMPTM ≤T ATM . This shows that Turing
reduction is more liberal than mapping reduction. Every mapping reduc-
tion is a valid Turing reduction but not vice-versa. Turing reduction is
not sensitive to complementation. Thus, for example, one can easily2 show
that ATM ≤T ATM which is of course not possible with mapping reduc-
tion.
Here is the basic result about Turing reduction.
Theorem 8. If A ≤T B and if A is undecidable then B is also undecidable.
If B is decidable then A is decidable.
Thus, if we want to show undecidability Turing reduction is enough. Map-
ping reductions are harder to construct but they give more information.
It is sometimes hard for beginners to see the real difference between mapping
reduction and Turing reduction in specific instances. If we look closely at
the Turing reductions above we asked the oracle a question and we did some
post-processing on the oracle’s answer. In mapping reduction we packaged
a question to the oracle (this is what f does) but we do not get to do
anything with the answer other than return it; we cannot even negate it.
More generally, with Turing reduction we can ask the oracle many questions
but with mapping reduction we get just one question and no post-processing
of the answer.
Turing reduction is deep and interesting but we will not explore it in any
depth. We will only use it to establish undecidability.
2Indeed this is trivial, make sure you understand this.
5