Recursion - Java Concepts - page 831

R ANDOM F ACT 13.1: The Limits of Computation

Have you ever wondered how your instructor or grader makes sure your
programming homework is correct? In all likelihood, they look at your solution and
perhaps run it with some test inputs. But usually they have a correct solution
available. That suggests that there might be an easier way. Perhaps they could feed
your program and their correct program into a Ȓprogram comparatorȓ, a computer
program that analyzes both programs and determines whether they both compute the
same results. Of course, your solution and the program that is known to be correct
need not be identicalȌwhat matters is that they produce the same output when given
the same input.

How could such a program comparator work? Well, the Java compiler knows how to
read a program and make sense of the classes, methods, and statements. So it seems
plausible that someone could, with some effort, write a program that reads two Java
programs, analyzes what they do, and determines whether they solve the same task.
Of course, such a program would be very attractive to instructors, because it could
automate the grading process. Thus, even though no such program exists today, it
might be tempting to try to develop one and sell it to universities around the world.

However, before you start raising venture capital for such an effort, you should know
that theoretical computer scientists have proven that it is impossible to develop such
a program, no matter how hard you try.

There are quite a few of these unsolvable problems. The first one, called the halting
problem, was discovered by the British researcher Alan Turing in 1936 (see photo
below). Because his research occurred before the first actual computer was
constructed, Turing had to devise a theoretical device, the Turing machine, to explain
how computers could work. The Tur ing machine consists of a long magnetic tape, a
read/write head, and a program tha t has numbered instructions of the form: "If the
current symbol under the head is x, then replace it with y, move the head one unit left
or right, and continue with instruction n" (see A Turing Machine). Interestingly
enough, with only these instructions, you can program just as much as with Java,
even though it is incredibly tedious to do so. Theoretical computer scientists like
Turing machines because they can be described using nothing more than the laws of
mathematics.

608
609