Discrete Mathematics for Computer Science

318 CHAPTER 5 Analysis of Algorithms

If A is not a legal algorithm, or if running A on input In causes a run-time error (such

as treating the letter s as a digit), our convention is that A halts on input In and returns the

empty string.

5.5.1 The Halting Problem

Recall the term decision problem from Section 5.3.5.

Definition 2. A set D of strings is decidable if there is a decision algorithm A that, for

an arbitrary string d, returns A(d) = TRUE if d e D and A(d) = FALSE if d ý D. A set

D that is not decidable is called undecidable.

By definition, a decision algorithm cannot have run-time errors. A decision algorithm

must always halt. It cannot run on forever (for example, in an infinite loop).

Given the expectations many people have for the power of the computer, it is perhaps

surprising to find basic problems for which no algorithms exist. The standard example,

credited to Alan Turing (1912-1954, b. England), is:

The Halting Problem

Given an algorithm A and an input In, will A ultimately halt on In, or will it run on

forever?

Here, A need not be a decision algorithm. It may stop and return the empty string. Thus,

it is assumed that A is an algorithm for a partial function, and the problem is to determine

whether A(In) is defined or undefined.

Now, we simply recast our discussion in terms of making a decision about a set of

strings. To do this, we use a string-say, %%-that we assume does not occur elsewhere

in the programming language. We just use it as a separator, so that a program can easily

extract, from a concatenated string S1 %%s2, the two separate strings s, and s2.

Definition 3. The halting problem is the set Halt of all strings A%%In where A is an

algorithm and A halts on input In.

The reader may think of it as being odd to input an algorithm as data to a program.

However, since an algorithm is a string, it is perfectly legal to do so. Even so, using an

algorithm as data is, indeed, common. For example, a compiler is a program that takes in

one program (in a "high-level" language) as input and returns a translated program (in a

"low-level" language). Also, a computer itself may take two strings of data (a machine-

language program and a data file), and run the program on the data file. Here, it is possible

that A halts on input In and returns the empty string. In this case, the string A%%In C Halt.

An algorithm H solves the halting problem if it is a decision algorithm for the set

D = Halt. In other words, H is an algorithm with the following properties:

1. H is a legal algorithm with no run-time errors, since it cannot return the empty string.


2. H halts on all inputs, since it must return TRUE or FALSE on every input.


3. If an arbitrary string d belongs to Halt, then H returns TRUE on input d.