The Turing Machine Halting Problem
We begin with some problems that have historical significance and that at the
same time give us a starting point for developing later results. The best-known of
these is the Turing machine halting problem. Simply stated, the problem is:
Given the description of a Turing machine M and an input w, does M, when
started in the initial configuration q 0 w, perform a computation that eventually
halts? Using an abbreviated way of talking about the problem, we ask whether M
applied to w, or simply (M,w), halts or does not halt. The domain of this problem
is to be taken as the set of all Turing machines and all w; that is, we are looking
for a single Turing machine that, given the description of an arbitrary M and w,
will predict whether or not the computation of M applied to w will halt.
We cannot find the answer by simulating the action of M on w, say by
performing it on a universal Turing machine, because there is no limit on the
length of the computation. If M enters an infinite loop, then no matter how long
we wait, we can never be sure that M is in fact in a loop. It may simply be a case
of a very long computation. What we need is an algorithm that can determine the
correct answer for any M and w by performing some analysis on the machine's
description and the input. But as we now show, no such algorithm exists.
For subsequent discussion, it is convenient to have a precise idea of what we
mean by the halting problem; for this reason, we make a specific definition of
what we stated somewhat loosely above.
Definition 12.1
Let w M be a string that describes a Turing machine M = (Q,Σ,Γ,δ,q 0 , ,F ), and let
w be a string in M’s alphabet. We will assume that w M and w are encoded as a
string of 0’s and 1’s, as suggested in Section 10.4. A solution of the halting
problem is a Turing machine H, which for any w M and w performs the
computation
if M applied to w halts, and
We begin with some problems that have historical significance and that at the
same time give us a starting point for developing later results. The best-known of
these is the Turing machine halting problem. Simply stated, the problem is:
Given the description of a Turing machine M and an input w, does M, when
started in the initial configuration q 0 w, perform a computation that eventually
halts? Using an abbreviated way of talking about the problem, we ask whether M
applied to w, or simply (M,w), halts or does not halt. The domain of this problem
is to be taken as the set of all Turing machines and all w; that is, we are looking
for a single Turing machine that, given the description of an arbitrary M and w,
will predict whether or not the computation of M applied to w will halt.
We cannot find the answer by simulating the action of M on w, say by
performing it on a universal Turing machine, because there is no limit on the
length of the computation. If M enters an infinite loop, then no matter how long
we wait, we can never be sure that M is in fact in a loop. It may simply be a case
of a very long computation. What we need is an algorithm that can determine the
correct answer for any M and w by performing some analysis on the machine's
description and the input. But as we now show, no such algorithm exists.
For subsequent discussion, it is convenient to have a precise idea of what we
mean by the halting problem; for this reason, we make a specific definition of
what we stated somewhat loosely above.
Definition 12.1
Let w M be a string that describes a Turing machine M = (Q,Σ,Γ,δ,q 0 , ,F ), and let
w be a string in M’s alphabet. We will assume that w M and w are encoded as a
string of 0’s and 1’s, as suggested in Section 10.4. A solution of the halting
problem is a Turing machine H, which for any w M and w performs the
computation
if M applied to w halts, and