
124
9.1 YES/NO PROBLEMS
We will only deal with ?yes/no problems?, so that we can ignore the
output of a Turing machine, only considering whether it halts and succeeds
or halts & fails. This simplification will be especially helpful when we
consider nondeterministic Turing machines (?10).
9.1.1 Definition
A yes/no problem is one with answer yes or no. Each yes/no problem has a
set of instances ? the set of valid inputs for that problem. The yesinstances of
a problem are those instances for which the answer is ?yes?. The others are
the noinstances.
9.1.2 Examples
Many problems can be put in yes/no form:
Problem instances yesinstances noinstances
Is w a prime
number?
binary
representations of
numbers
binary
representations of
primes
binary
representations of
nonprimes
Halting problem:
Does M halt on
input w?
all pairs (code(M),w)
where M is a
standard TM, and
w a word of C
all those pairs
(code(M),w) such
that M halts &
succeeds on w
the pairs
(code(M),w) such
that M doesn't halt
& succeed on w
HCP all (finite) graphs graphs with a
Hamiltonian circuit
graphs with no
Hamiltonian circuit
TSP all pairs (G,d),
where G is a
weighted graph,
and d?0
all pairs (G,d) such
that G has a
Hamiltonian circuit
of length ?d
all pairs (G,d) such
that G has no
Hamiltonian circuit
of length ?d
Even if we ignore its output, a Turing machine can still ?communicate?
with us by halting & succeeding (?yes?), or halting & failing (?no?), so it can
answer yes/no problems. Of course, we may have to code the instances of
the problem as words, so they can be input to a Turing machine. For HP,
code(M) is given to the TM, as M itself is a machine, not a word. The coding
of instances into words should be reasonable: we do not allow unary
representation of numbers, and cheating (such as coding all yesinstances as
?yes? and all noinstances as ?no?) is not allowed.
9.1.3 Acceptance, rejection, solving
1. A Turing machine M is said to accept a word w of its input alphabet if
M halts and succeeds on input w.
2. M is said to reject w if M halts and fails on input w.
125
3. A Turing machine M is said to solve a yes/no problem A if:
? every instance of A is a word of the input alphabet of M (or can
be coded as one in a reasonable way);
? M accepts all the yesinstances of A;
? M rejects all the noinstances of A.
9.1.3.1 Example
1. In ?3.3.4 we saw a Turing machine that halts and succeeds if its input
word is a palindrome, and halts & fails if not. This machine solves the
yes/no problem is w ? I* a palindrome?, where I is its input alphabet.
2. The universal Turing machine U does not solve the halting problem. If
we give it code(M)*w for some standard M and word w?C*, then U does halt
& succeed on the yesinstances (see the table above). But it does not halt &
fail on all the noinstances: if M runs forever on w, U never halts on
code(M)*w.
9.1.3.2. Our problems must have infinitely many y and ninstances
We do not consider yes/no problems with only finitely many yesinstances,
or only finitely many noinstances. They are too easy. E.g., if the
yesinstances of a yes/no problem X are just y1,?,yn, a Turing machine M
can ?solve? X by checking to see if the input word w is one of the yi. (The yi
are ?hardwired? into M; we can do this as there are only finitely many of
them.) If it is, M halts and succeeds; otherwise it halts and fails. No
?calculation? is involved. E.g., ?Is 31 prime?? has no instances at all, and is
solved by the trivial Turing machine whose initial state is halting.
This may seem odd. For example, one of the Turing machines in Fig. 9.1
(both with input alphabet C, say) solves the yes/no problem:
?Is (a) Goldbach's conjecture true, and (b) w = w??
The instances of this problem are all words w of C. The yesinstances are
those w such that (a) Goldbach's conjecture is true, and (b) w=w. The noinstances
are the rest. So if the conjecture is true, every w?C* is a yesinstance,
so Y solves it (Y halts & succeeds on any input). If not, every w?C*
is a noinstance, so N solves it (N halts & fails on any input). Of course, we
don't know which! But the problem is solvable ? either by Y or by N.
Y N
9.1 Which machine solves Goldbach's conjecture?
For a problem to be solvable according to our definition, we are only concerned that a Turing machine solution exists, not in how to find it. So