H and does the opposite; if H outputs “halt,” then N loops, and if H out-
puts “loop,” then N halts.
Since H presumably is able to determine whether a program halts or
not, let’s take the program N and use it as the input to N. If H determines
that N halts, then the output of H is “halt,” and so N loops. If H deter-
mines that N loops, then the output of H is “loop,” and so N halts. In
other words, N does the opposite of what H thinks it should do. This con-
tradiction resulted from our assumption that the halting problem was
solvable; therefore, the halting problem must be unsolvable.
That probably wasn’t so hard to follow. It looks like the proof incorpo-
rates elements similar to those that existed in the liar’s paradox, and looks
are not deceptive in this case. Mathematicians have shown that even
though the results appear to be in disparate areas, Gödel’s theorem and
the unsolvability of the halting problem are equivalent; each can be proved
as a consequence of the other.
Flash forward to the present. The unsolvability of the halting problem
turns out to be equivalent to a problem whose unsolvability will probably
ensure the continued existence of a multibillion dollar industry. The year
2007 marked the twenty-fifth anniversary of the first appearance of a
computer virus. The Elk Cloner virus was developed for Apple II comput-
ers by Rich Skrenta, a Pittsburgh high-school student, and did nothing
more sinister than copy itself to operating systems and f loppy disks (re-
member them?), and display the following less-than-memorable verse on
the monitor screen.
Elk Cloner: The program with a personality
It will get on all your disks
It will infiltrate your chips
Yes it’s Cloner!
It will stick to you like glue
It will modify RAM too
Send in the Cloner!^6Skrenta was to prove no threat to Keats or Frost as a literary figure, but
from this humble effort sprung the whole spectrum of malware. It also
resulted in the obvious question: Is it possible to write a program that
will detect computer viruses? Happily for the continued existence of
firms such as Norton and McAfee, computer programs can be written to
detect some viruses, but the criminals will always be ahead of the police,
at least in this area. The existence of a computer program to detect all
126 How Math Explains the World