[Overview] [Previous] [Next]

The Halting Problem I

Turing machines sometimes halt, and sometimes they enter an infinite loop. A Turing machine might halt for one input string, but go into an infinite loop when given some other string. The halting problem asks: Is it possible to tell, in general, whether a given machine will halt for some given input?

If it is possible, then there is an effective procedure to look at a Turing machine and its input and determine whether the machine will halt with that input. If there is an effective procedure, then we can build a Turing machine to implement it.

We will now prove that the halting problem is insoluable.

Copyright 1996 by David Matuszek
Last modified Apr 14, 1996