Computability Theory Fall 2020

Lecture 10: Reducibility

Lecturer: Renjie Yang

10.1 Decision Problem

Definition 10.1 The decision problem for a predicate P px1 , . . . , xn q is called recursively solvable
if P is recursive; otherwise it is called recursively unsolvable.

Definition 10.2 The decision problem for a set S is called recursively solvable or unsolvable ac-
cording as S is or is not recursive.

Definition 10.3 Let A be a set, and let Σ be a alphabet. An encoding of the elements of A, using
Σ, is an injective function Enc : A Ñ Σ˚ . We denote the encoding of a P A by xay. If w P Σ˚ is
such that there is some a P A with w “ xay, then we say w is a valid encoding of an element in A.
A set that can be encoded is called encodable.

Example

• Problem: Given a DFA and a string, will the DFA accept?

• The same problem in terms of languages: Given a DFA B and a string w, is xB, wy a member
of the language ADF A “ txB, wy|B is a DFA that accepts input string wu?

• Decision problem: Is the language ADF A decidable?

• The answer to this decision problem is yes. Here is a Turing machine that decides ADF A :
MA “ “On input xB, wy,

1. Check that xB, wy has length 2, xBy is an encoding of DFA. If not, reject;
2. Simulate B on input w
3. If the simulation ends in an accept state, accept . If it ends in a nonaccepting state,
reject.”

Example

• Problem: Given a DFA, will the DFA accept any string?

• The same problem in terms of languages: Given a DFA B, is B a member of the language
EDF A “ txB, wy|B is a DFA and LpBq “ φu?

• Decision problem: Is the language EDF A decidable?

• The answer to this decision problem is yes. Here is a Turing machine that decides EDF A :
ME “ “On input xB, wy,

1. Check that xBy is an encoding of DFA. If not, reject;

2. Mark the start state of B;

1
 3. Repeat until no new states get marked:
Mark any state that has a transition coming into it from any state that is already marked.
4. If no accept state is marked, accept; otherwise, reject.”

Example

• Problem: Given two DFAs, do they recognize the same language?

• The same problem in terms of languages: Given two DFAs A and B, is xA, By a member of
the language EQDF A “ txA, By|A and B are DFAs and LpAq “ LpBqu?

• Decision Problem: Is the language EQDF A decidable?

• The answer to this decision problem is yes. Here is a Turing machine that decides EQDF A :
MEQ “ “On input xA, By,

1. Check that xA, By has length 2, xBy and xAy are encodings of DFA. If not, reject;
2. Construct a DFA C such that LpCq “ pLpAq X LpBqq Y pLpAq X LpBqq;
3. Run TM ME on input xCy;
4. If ME accepts, accept. If ME rejects, reject.”

Example

• Problem: Given a Turing machine and a string, will the Turing machine accept?

• The same problem in terms of languages: Given a TM M and a string w, is xM, wy a member
of the language AT M “ txM, wy|M is a TM that accepts input string wu?

• Decision problem: Is the language AT M decidable?

• The answer to this decision problem is NO.

Theorem 10.4 AT M is undecidable.

Proof: Assume that AT M is decidable. Then there exists a Turing machine H which is a decider
for AT M : #
accept, if M accepts w,
HpxM, wyq “
reject, if M does not accept w.
Construct a new Turing machine D as follows:
#
accept, if M does not accept xM y,
DpxM yq “
reject, if M accepts xM y.

Now apply D on xDy:

#
accept, if D does not accept xDy,
DpxDyq “
reject, if D accepts xDy.

Contradiction. Therefore the assumption that AT M is decidable is false.

2
Example
• Given a Turing machine and a string, will the Turing machine halt?

• The same problem in terms of languages: Given a Turing machine M and a string w, is
xM, wy a member of the language HALTT M “ txM, wy|M is a TM that halts on string wu?

• Decision problem: Is the language HALTT M decidable?

• The same decision problem in terms of predicates: Is the predicate PZ pxq Ø “x is the Gödel number of
an instantaneous description α of Z and there exists a computation of Z that begins with α2
computable or recursively solvable?

• The answer to this decision problem is NO.

Theorem 10.5 HALTT M is undecidable.

Proof: Assume a Turing machine R decides HALTT M . Construct another Turing machine S to
decide AT M :
S “ “On input xM, wy,
1. Check that xM, wy has length 2, xM y is an encoding of a Turing machine. If not, reject;

2. Run Turing machine R on input xM, wy;

3. If R rejects, reject;

4. If R accepts, simulate M on w until it halts.

5. If M has accepted, accept. If M has rejected, reject.”

Here is another proof. Let Z0 be such that ΨZ0 pxq “ miny T px, x, yq. Then x belongs to the
domain of ΨZ0 pxq if and only if DyT px, x, yq. But x belongs to the domain of ΨZ0 pxq if and only
if PZ0 pgnpq1 xqq. Hence, if PZ0 pxq were computable, so would be the domain of ΨZ0 pxq, and hence
also the predicate DyT px, x, yq. But DyT px, x, yq is not computable, contradiction.

Example
• Problem: Does a Turing machine accept any string?

• The same problem in terms of languages: Given a Turing machine M , is xM y a member of

the language ET M “ txM y|M is a Turing machine and LpM q “ φu?

• Decision problem: Is the language ET M decidable?

• The answer to this decision problem is NO.

Theorem 10.6 ET M is undecidable.

Proof: We will use a modification of M constructed as follows:

M1 “ “On input xxy,
1. If x ‰ w, reject;

2. If x “ w, run M on input w and accept if M does.”

3
Assume that Turing machine R decides ET M . We can construct a Turing machine S that decides
AT M as follows:
S “ “On input xM, wy,

1. Check that xM, wy has length 2, xM y is an encoding of a Turing machine. If not, reject;

2. Use the description of M and w to construct the Turing machine M1 described above;

3. Run R on input xM1 y;

4. If R accepts, reject; if R rejects, accept.”

If R were a decider for ET M , S would be a decider for AT M . A decider for AT M does not exist,
contradiction. Therefore ET M is undecidable.

Example

• Problem: Given two Turing machines, do they accept the same language?

• The same problem in terms of languages: Given Turing machines M1 and M2 , is xM1 , M2 y a
member of the language EQT M “ txM1 , M2 y|M1 and M2 are Turing machines and LpM1 q “
LpM2 qu?

• Decision problem: Is the language EQT M decidable?

• The answer to this decision problem is NO.

Theorem 10.7 EQT M is undecidable.

Proof: Assume That Turing machine R decides EQT M . Construct a decider S of ET M as follows:
S “ “On input xM y,

1. Check that xM y is an encoding of a Turing machine. If not, reject;

2. Run R on input xM, M1 y, where M1 is a Turing machine that rejects all inputs.

3. If R accepts, accept; if R rejects, reject.”

If R decides EQT M , S decides EEM . But ET M is undecidable, contradiction. Therefore EQT M is

undecidable.

10.2 Reducibility
Definition 10.8 Let A and B be sets. then A is said to be many-one reduction (or mapping
reduction) to B, written A ďm B, if there is a computable function f such that for every natural
number x,

x P A if and only if f pxq P B

Example Define K “ tx| ϕx pxqu, K0 “ txi, xy| ϕi pxq Óu. There is a computable function f : x Ñ
xx, xy such that x P K if and only if xx, xy P K0 . Therefore K ďm K0 .

Theorem 10.9 If A ďm B and B ďm C, then A ďm C

4
Proof: Let f be the reduction function of A to B, g be the reduction function of B to C. Then

x P A if and only if f pxq P B if and only if g ˝ f pxq P C.

g ˝ f is the reduction function of A to C.

Theorem 10.10 Let A and B be any sets, A ďm B.

• If B is computably enumerable, so is A.

• If B is computable, so is A.

Proof: If B is the domain of partial function g, then A is the domain of g ˝ f :

x P A Ø f pxq P B Ø gpf pxqq Ó

Thus the first claim is true.

For the second claim, since x P A Ø f pxq P B, CA pxq “ CB pf pxqq for any x, CA “ CB ˝ f . If CB
is computable, then CA is also computable.

Example Let K1 “ te| ϕe p0qu. K1 is computably enumerable but not computable.

Proof: It is suffices to show that K0 is reducible to K1 . Since T predicate is primitive recursive,

according to the normal form theorem for r.e. sets, K1 is computably enumerable. To show that
K1 is not computable, let f be the 3-ary function defined by

f px, y, zq » ϕx pyq.

Pick an index e such that f “ ϕ3e , we have

ϕ3e px, y, zq » ϕx pyq.

By the s-m-n theorem, there is a function spe, x, yq (more precisely, s21 pe, x, yq) such that, for every
z,
ϕspe,x,yq pzq » ϕ3e px, y, zq » ϕx pyq.
spe, x, yq is an index for the machine that, for any input z, ignores that input and computes ϕx pyq.
In particular, we have
ϕspe,x,yq p0q Ó if and only if φx pyq Ó .
Therefore, xx, yy P K0 if and only if spe, x, yq P K1 . So the function g defined by

gpwq “ spe, Kpwq, Lpwqq

is a reduction of K0 to K1 .

Example Let T ot “ tx| for every y, ϕx pyq Óu. Then T ot is not computable.

Proof: It is suffices to show that K is reducible to T ot. Define hpx, yq as

#
0, if x P K
hpx, yq »
undefined, otherwise

5
hpx, yq is just N pU pmins T px, x, sqqq, so it is partially computable. By the s-m-n theorem, there is
a primitive recursive function spxq such that for every x and y,
#
0, if x P K
ϕspxq pyq » hpx, yq »
undefined, otherwise

So ϕspxq is total if x P K, and undefined otherwise. Thus, s is a reduction of K to T ot.

Theorem 10.11 (Rice’s Theorem) Let C be any set of partial computable functions, and let A “
tn| ϕn P Cu. If A is computable, then either C is φ or C is the set of all the partial computable
functions.

Proof: Let g be any function in C, and f is the function that is nowhere defined. Without loss of
generality, assume f R C. Define hpx, yq » P12 pgpyq, U npx, xqq. That is to say,
#
undefined, if ϕx pxq Ò
hpx, yq »
gpyq, otherwise

Since hpx, yq is a composition of partial computable functions, it is a partial computable function,

therefore it is equal to function ϕk for some index k. By the s-m-n theorem there is a primitive
recursive function s such that for each x,

ϕspk,xq pyq “ ϕk px, yq “ hpx, yq.

Now for each x, if φx pxq Ó, then φspk,xq is the same function as g, and so spk, xq is in A. On the
other hand, if φx pxq Ò, then ϕspk,xq is the same function as f , so spk, xq is not in A. In other words,
we have that for every x, x P K if and only if spk, xq P A. If A were computable, then K would
also be computable, contradiction. So A is not computable.