Limits to Computation - Data Structures and Algorithm Analysis

Java Reference

In-Depth Information

a function as part of a program) to take P and some input string w, and

modify it so that w is hardcoded inside P, with P reading no input. Call this

modified program P 0 . Now, P 0 always behaves the same way regardless of

its input, because it ignores all input. However, because w is now hardwired

inside of P 0 , the behavior we get is that of P when given w as input. So, P 0

will halt on any arbitrary input if and only if P would halt on input w. We

now feed P 0 to function Ahalt . If Ahalt could determine that P 0 halts

on some input, then that is the same as determining that P halts on input w.

But we know that that is impossible. Therefore, Ahalt cannot exist. 2

There are many things that we would like to have a computer do that are un-

solvable. Many of these have to do with program behavior. For example, proving

that an arbitrary program is “correct,” that is, proving that a program computes a

particular function, is a proof regarding program behavior. As such, what can be

accomplished is severely limited. Some other unsolvable problems include:

• Does a program halt on every input?

• Does a program compute a particular function?

• Do two programs compute the same function?

• Does a particular line in a program get executed?

This does not mean that a computer program cannot be written that works on

special cases, possibly even on most programs that we would be interested in check-

ing. For example, some C compilers will check if the control expression for a

while loop is a constant expression that evaluates to false . If it is, the compiler

will issue a warning that the while loop code will never be executed. However, it

is not possible to write a computer program that can check for all input programs

whether a specified line of code will be executed when the program is given some

specified input.

Another unsolvable problem is whether a program contains a computer virus.

The property “contains a computer virus” is a matter of behavior. Thus, it is not

possible to determine positively whether an arbitrary program contains a computer

virus. Fortunately, there are many good heuristics for determining if a program

is likely to contain a virus, and it is usually possible to determine if a program

contains a particular virus, at least for the ones that are now known. Real virus

checkers do a pretty good job, but, it will always be possible for malicious people

to invent new viruses that no existing virus checker can recognize.

17.4