[Overview] [Previous] [Next]

The Halting Problem II

This page uses Boolean functions, written in a pseudo-programming language, because I think they are easier for most people to understand than a strictly formal Turing-machine notation. Except for notation, the argument presented here is exactly the same as the one in your textbook.

Suppose we have a Turing machine WillHalt which, given an input string M+w, will halt and accept the string if Turing machine M halts on input w, and will halt and reject the string if Turing machine M does not halt on input w. Viewed as a Boolean function, WillHalt(M,w) halts and returns true in the first case, and halts and returns false in the second.

We will prove by contradiction that

Theorem. Turing machine WillHalt(M,w) cannot exist.