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 non-deterministic 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 yes-instances of a problem are those instances for which the answer is ?yes?. The others are the no-instances.

9.1.2 Examples
Many problems can be put in yes/no form:
Problem instances yes-instances no-instances Is w a prime
number?
binary
representations of
numbers

binary
representations of
primes

binary
representations of
non-primes
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 yes-instances as ?yes? and all no-instances 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 yes-instances of A;
? M rejects all the no-instances 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 yes-instances (see the table above). But it does not halt & fail on all the no-instances: 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 n-instances We do not consider yes/no problems with only finitely many yesinstances, or only finitely many no-instances. They are too easy. E.g., if the yes-instances 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 ?hard-wired? 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 yes-instances 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 no-instance, 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