210 CHAPTER 4 / DECIDABILITY

For the other direction, if both A and A are Turing-recognizable, we let M1

be the recognizer for A and M2 be the recognizer for A. The following Turing
machine M is a decider for A.
M = “On input w:
1. Run both M1 and M2 on input w in parallel.
2. If M1 accepts, accept ; if M2 accepts, reject .”
Running the two machines in parallel means that M has two tapes, one for simu-
lating M1 and the other for simulating M2 . In this case, M takes turns simulating
one step of each machine, which continues until one of them accepts.
Now we show that M decides A. Every string w is either in A or A. There-
fore, either M1 or M2 must accept w. Because M halts whenever M1 or M2
accepts, M always halts and so it is a decider. Furthermore, it accepts all strings
in A and rejects all strings not in A. So M is a decider for A, and thus A is
decidable.

COROLLARY 4.23
ATM is not Turing-recognizable.

PROOF We know that ATM is Turing-recognizable. If ATM also were Turing-

recognizable, ATM would be decidable. Theorem 4.11 tells us that ATM is not
decidable, so ATM must not be Turing-recognizable.

EXERCISES
A
4.1 Answer all parts for the following DFA M and give reasons for your answers.

a. Is 〈M, 0100〉 ∈ ADFA ? d. Is 〈M, 0100〉 ∈ AREX ?

b. Is 〈M, 011〉 ∈ ADFA ? e. Is 〈M 〉 ∈ EDFA ?
c. Is 〈M 〉 ∈ ADFA ? f. Is 〈M, M 〉 ∈ EQ DFA ?
 PROBLEMS 211

4.2 Consider the problem of determining whether a DFA and a regular expression are
equivalent. Express this problem as a language and show that it is decidable.
4.3 Let ALLDFA = {〈A〉| A is a DFA and L(A) = Σ∗ }. Show that ALLDFA is decidable.
4.4 Let AεCFG = {〈G〉| G is a CFG that generates ε}. Show that AεCFG is decidable.
A
4.5 Let ETM = {〈M 〉| M is a TM and L(M ) = ∅}. Show that ETM , the complement of
ETM , is Turing-recognizable.
4.6 Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the
functions f : X−→ Y and g : X−→ Y in the following tables. Answer each part
and give a reason for each negative answer.

n f (n) n g(n)
1 6 1 10
2 7 2 9
3 6 3 8
4 7 4 7
5 6 5 6

A A
a. Is f one-to-one? d. Is g one-to-one?
b. Is f onto? e. Is g onto?
c. Is f a correspondence? f. Is g a correspondence?

4.7 Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable
using a proof by diagonalization.
4.8 Let T = {(i, j, k)| i, j, k ∈ N }. Show that T is countable.
4.9 Review the way that we define sets to be the same size in Definition 4.12 (page 203).
Show that “is the same size” is an equivalence relation.

PROBLEMS
A
4.10 Let INFINITE DFA = {〈A〉| A is a DFA and L(A) is an infinite language}. Show
that INFINITEDFA is decidable.
4.11 Let INFINITE PDA = {〈M 〉| M is a PDA and L(M ) is an infinite language}. Show
that INFINITE PDA is decidable.
A
4.12 Let A = {〈M 〉| M is a DFA that doesn’t accept any string containing an odd num-
ber of 1s}. Show that A is decidable.
4.13 Let A = {〈R, S〉| R and S are regular expressions and L(R) ⊆ L(S)}. Show that
A is decidable.
A
4.14 Let Σ = {0,1}. Show that the problem of determining whether a CFG generates
some string in 1∗ is decidable. In other words, show that

{〈G〉| G is a CFG over {0,1} and 1∗ ∩ L(G) = ∅}

is a decidable language.