Mr. Turing’s amazing machines - The Computing Universe: A Journey through a Revolution - page 113

The origin of this contradiction can be traced back to our assumption that
machine D exists. Therefore no such machine can exist and this shows that the
halting problem is not decidable. Using such techniques, Turing was able to
demonstrate an unsolvable problem: in so doing, he had shown that Hilbert's
Entscheidungsproblem has no solution.
The halting problem has a number of important implications. In writing
programs we would naturally like to be able to check whether our program
actually does do what it is supposed to do. This turns out to be a decision
problem. We need to input a description of the algorithmic problem and the
text of our program implementing an algorithm that we think solves the
problem. We want a “yes” if, for all of the legal inputs for the problem, our
algorithm will terminate and give the correct solution; and we want a “no” if
there is any input for which our program fails to terminate or gives the wrong
result. Now we know about the halting problem we can see immediately that
such an automatic verifier is not possible. However, although we cannot guar-
antee that our program will halt for all inputs, it is still possible to produce
formal verification tools that can deliver useful results most of the time!
In another application, Fred Cohen, in 1986 in his doctoral thesis for
the University of Southern California, showed that the problem of detecting
the presence of a computer virus was an instance of the halting problem.
Unfortunately this means that the general problem of identifying a virus cannot
be solved. We will have more to say about computer viruses in a later chapter.

Key concepts

Hilbert's Entscheidungsproblem (decision problem)

Turing machines

M

M

Natural, integer, and rational numbers

M

Irrational numbers and effective procedures M

Computable and noncomputable numbers M

Universal Turing Machines

M

Church-Turing thesis M

The halting problem M