7.1.3   The Halting Problem

The Halting Problem, simply stated, is: does there exist a computer program that
takes an arbitrary program, P_i, and an arbitrary set of inputs, I_j, and determines
whether or not P_i will halt on I_j (Figure 7.1). The question of the existence of
such an oracle is more than a theoretical exercise, and it has important implications
in the development of process monitors, program verification, and in
schedulability analysis. Unfortunately, such an oracle cannot be built.¹ Thus the
Halting Problem is unsolvable. There are several ways to demonstrate this surprising
fact. One way is using Cantor’s diagonal argument, first used to show
that the real numbers are not countably denumerable.

It should be clear that every possible program, in any computer language, can
be encoded using a numbering scheme in which each program is represented as
the binary expansion of the concatenated source-code bytes. The same encoding
can be used with each input set. Then if the proposed oracle could be built, its
behavior would be described in tabular form as in Table 7.1. That is, for each
program P_i and each input set I_j it would simply have to determine if program P_i
halts on I_j. Such an oracle would have to account for every conceivable program
and input set.

In Table 7.1, the ↑ symbol indicates that the program does not halt and the
symbol ↓ indicates that the program will halt on the corresponding input. However,
the table is always incomplete in that a new program P* can be found

that differs from every other in at least the input at the diagonal. Even with the
addition of a new program P*, the table cannot be completed because a new
P* can be added that is different from every other program by using the same
construction.

To see the relevance of the Halting Problem to real-time systems suppose a
schedulability analyzer is to take an arbitrary program and the set of all possible
inputs to that program and determine the best-, worst-, and average-case execution
times for that program (Figure 7.2).

A model of the underlying machine is also needed, but this can be incorporated
as part of the input set. It is easy to see that is a manifestation of the Halting
Problem, since in order to determine the running time, the analyzer must know
when (and hence, if) the program stops. While it is true that given a program in
a specific language and a fixed set of inputs, the execution times can be found,
the running times can be determined only through heuristic techniques that are
not generalizable, that is, they could not work for an arbitrary and dynamic set
of programs.

The Halting Problem also has implications in process monitoring. For example,
is a process deadlocked or simply waiting? And also in the theory of recursive
programs, for example, will a recursive program finish referencing itself?

____________________________________________
¹Strictly speaking, such an oracle can be built if it is restricted to a computer with fixed-size
memory since, eventually, a maximum finite set of inputs would be reached, and hence the table
could be completed.