[Overview] [Previous] [Next]
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
will halt and accept the string if Turing machine
M halts on input
and will halt and reject the string if Turing machine
M does not halt on
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.