
Limits of Computation ◾ 311
whether any given computer program halts when it is executed. Let’s call
the assumed algorithm HaltChecker.
ink of HaltChecker as a computer program that accepts as input
another program. (Perhaps this other program is read from a le.) e pur-
pose of HaltChecker is to determine whether the other program will halt.
Figure10.16 depicts HaltChecker as black box machine. Another pro-
gram, labeled “any program” in the gure, is input to the box aer which
the algorithm in the box lights one of two lights (“will halt” or “will not
halt”).
Now consider the following program; call it InterestingProgram: