Java Reference
In-Depth Information
610
Expressed in terms of Java, the halting problem states: ȒIt is impossible to write a
program with two inputs, namely the source code of an arbitrary Java program P and
a string I, and that decides whether the program P, when executed with the input I,
will halt without getting into an infinite loopȓ. Of course, for some kinds of
programs and inputs, it is possible to decide whether the program halts with the
given input. The halting problem asserts that it is impossible to come up with a
single decision-making algorithm that works with all programs and inputs. Note that
you can't simply run the program P on the input I to settle this question. If the
program runs for 1,000 days, you don't know that the program is in an infinite loop.
Maybe you just have to wait another day for it to stop.
Such a Ȓhalt checkerȓ, if it could be written, might also be useful for grading
homework. An instructor could use it to screen student submissions to see if they get
into an infinite loop with a particular input, and then stop checking them. However,
as Turing demonstrated, such a program cannot be written. His argument is
ingenious and quite simple.
Suppose a Ȓhalt checkerȓ program existed. Let's call it H. From H, we will develop
another program, the "killer" program K. K does the following computation. Its input
is a string containing the source code for a program R. It then applies the halt
checker on the input program R and the input string R. That is, it checks whether the
program R halts if its input is its own source code. It sounds bizarre to feed a
program to itself, but it isn't impossible. For example, the Java compiler is written in
Java, and you can use it to compile itself. Or, as a simpler example, a word counting
program can count the words in its own source code.
When K gets the answer from H that R halts when applied to itself, it is programmed
to enter an infinite loop. Otherwise K exits. In Java, the program might look like this:
public class Killer
{
public static void main(String[] args)
{
String r = read program input;
HaltChecker checker = new Haltchecker();
if (checker.check(r, r))
while (true) {} // Infinite loop
else
return;
Search WWH ::




Custom Search