next up previous
Next: Penrose's argument for computational Up: Contents Previous: Examples of Computations that

Deciding how computations stop - The Halting Problem

The answer to these questions is found in a profound, fundamental and important theorem of mathematical logic called ``Gödel's Incompleteness Theorem". Roughly it asserted (proved) that

tex2html_wrap288

For our purposes this theorem tells us that any set of formalized rules will be insufficient to determine whether an arbitrary computation will halt.



David T J Liley
Thu Apr 9 12:39:27 EST 1998