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.
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. When viewed as a Boolean function, “WillHalt (M, w)” halts and returns
“TRUE” in the first case, and (halts and) returns “FALSE” in the second.
THE O REM: Turing Machine “WillHalt (M, w)” does not exist.
Proof: This theorem is proved by contradiction.
Suppose we could build a machine “WillHalt”.
Then we can certainly build a second machine,
“LoopIfHalts”, that will go into an infinite loop if and only if “WillHalt”
accepts its input:
Func tion LoopIfHalts (M, w):
if WillHalt (M, w) then
while true do { }
else
return false;
We will also define a machine “LoopIfHaltOnItSelf” that, for any given
input M, representing a Turing machine, will determine what will happen if M
is applied to itself, and loops if M will halt in this case.
Func tion LoopIfHaltsOnItself (M):
return LoopIfHalts (M, M):
Finally, we ask what happens if we try:
Func tion Impos si ble:
return LoopIfHaltsOnItself (LoopIfHaltsOnItself):
This machine, when applied to itself, goes into an infinite loop if and only
if it halts when applied to itself. This is impossible. Hence the theorem is
proved.
200
Theory of Automata, Formal Languages and Computation
Start
Will this
program
halt?
Yes
Halt