774
Modeling Arithmetic, Computation, and Languages
Consider the following statement, which seems very similar: Given a particular (T, a) pair, does an algorithm exist to decide whether T halts when begun
on a tape containing a? Here, the (T, a) pair comes first and an algorithm is chosen based on the particular (T, a); for a different (T, a), there can be a different
algorithm. The statement has become (4(T, a))( E algorithm)(…). This problem
is solvable. Suppose someone gives us a (T, a). Two algorithms are (1) “say yes”
and (2) “say no.” Since T acting on a either does or does not halt, one of these
two algorithms correctly answers the question. This solution may seem trivial
or even sneaky, but consider again the problem statement: Given a particular
(T, a) pair, does an algorithm exist to decide, and so forth. Such an algorithm
does exist; it is either to say yes or to say no—we are not required to choose
which one is correct!
This turnabout of words changes the unsolvable halting problem into a trivially solvable problem. It also points out the character of a decision problem, asking
whether a single algorithm exists to solve a large class of problems. An unsolvable
problem has both a good side and a bad side. That no algorithm exists to solve a
large class of problems guarantees jobs for creative thinkers who cannot be replaced by Turing machines. But that the class of problems considered is so large
might make the result too general to be of interest.
We will state the halting problem again and then prove its unsolvability.
Definition hALtinG ProBLEM
The halting problem asks: Does an algorithm exist to decide, given any Turing machine T and string a, whether T begun on a tape containing a will eventually halt?
tHeoRem on thE hALtinG ProBLEM
The halting problem is unsolvable.
Proof: We want to prove that something does not exist, a situation made to order
for proof by contradiction. Therefore we assume that the halting problem is solvable and that a single algorithm exists that can act on any (T, a) pair as input and
eventually decide whether T running on a halts. We are asking this algorithm to
solve a task of symbol manipulation, since we can imagine the set of quintuples
of T encoded as some unique string s T of symbols; we’ll use (s T , a) to denote the
string s T concatenated with the string a. The task then becomes transforming the
string (s T , a) into a string representing a yes (the Turing machine with description s T halts when begun on a tape containing a) or a no (the Turing machine
with description s T does not halt when begun on a tape containing a). By the
Church–Turing thesis, because we have assumed the existence of an algorithm
that performs this task, we can assume the existence of a single Turing machine
X that performs this task. Thus X acts on a tape containing (s T , a) for any T and
a and eventually halts, at the same time telling us whether T on a halts. To be
definite, suppose that X begun on (s T , a) halts with a 1 left on the tape if and only
if T begun on a halts, and X begun on (s T , a) halts with a 0 left on the tape if and
only if T begun on a fails to halt; these are the only two possibilities. Figure 9.23
illustrates Turing machine X.
Modeling Arithmetic, Computation, and Languages
Consider the following statement, which seems very similar: Given a particular (T, a) pair, does an algorithm exist to decide whether T halts when begun
on a tape containing a? Here, the (T, a) pair comes first and an algorithm is chosen based on the particular (T, a); for a different (T, a), there can be a different
algorithm. The statement has become (4(T, a))( E algorithm)(…). This problem
is solvable. Suppose someone gives us a (T, a). Two algorithms are (1) “say yes”
and (2) “say no.” Since T acting on a either does or does not halt, one of these
two algorithms correctly answers the question. This solution may seem trivial
or even sneaky, but consider again the problem statement: Given a particular
(T, a) pair, does an algorithm exist to decide, and so forth. Such an algorithm
does exist; it is either to say yes or to say no—we are not required to choose
which one is correct!
This turnabout of words changes the unsolvable halting problem into a trivially solvable problem. It also points out the character of a decision problem, asking
whether a single algorithm exists to solve a large class of problems. An unsolvable
problem has both a good side and a bad side. That no algorithm exists to solve a
large class of problems guarantees jobs for creative thinkers who cannot be replaced by Turing machines. But that the class of problems considered is so large
might make the result too general to be of interest.
We will state the halting problem again and then prove its unsolvability.
Definition hALtinG ProBLEM
The halting problem asks: Does an algorithm exist to decide, given any Turing machine T and string a, whether T begun on a tape containing a will eventually halt?
tHeoRem on thE hALtinG ProBLEM
The halting problem is unsolvable.
Proof: We want to prove that something does not exist, a situation made to order
for proof by contradiction. Therefore we assume that the halting problem is solvable and that a single algorithm exists that can act on any (T, a) pair as input and
eventually decide whether T running on a halts. We are asking this algorithm to
solve a task of symbol manipulation, since we can imagine the set of quintuples
of T encoded as some unique string s T of symbols; we’ll use (s T , a) to denote the
string s T concatenated with the string a. The task then becomes transforming the
string (s T , a) into a string representing a yes (the Turing machine with description s T halts when begun on a tape containing a) or a no (the Turing machine
with description s T does not halt when begun on a tape containing a). By the
Church–Turing thesis, because we have assumed the existence of an algorithm
that performs this task, we can assume the existence of a single Turing machine
X that performs this task. Thus X acts on a tape containing (s T , a) for any T and
a and eventually halts, at the same time telling us whether T on a halts. To be
definite, suppose that X begun on (s T , a) halts with a 1 left on the tape if and only
if T begun on a halts, and X begun on (s T , a) halts with a 0 left on the tape if and
only if T begun on a fails to halt; these are the only two possibilities. Figure 9.23
illustrates Turing machine X.