SKEDSOFT

Halting Problem: The input to a Turing machine is a string. Turing machines themselves can be written as strings. Since these strings can be used as input to other Turing machines.

A “Universal Turing machine” is one whose input consists of a description M of some arbitrary Turing machine, and some input w to which machine M is to be applied, we write this combined input as M w. This produces the same output that would be produced by M. This is written as

Universal Turing Machine (M w) = M (w).

As a Turing machine can be represented as a string, it is fully possible to supply a Turing machine as input to itself, for example M (M). This is not even a particularly bizarre thing to do for example, suppose you have written a C pretty printer in C, then used the Pretty printer on itself. Another common usage is Bootstrapping—where some convenient languages used to write a minimal compiler for some new language L, then used this minimal compiler for L to write a new, improved compiler for language L. Each time a new feature is added to language L, you can recompile and use this new feature in the next version of the compiler. 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: “It is 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.

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.

THEOREM: 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:

Function LoopIfHalts (M, w):

if WillHalt (M, w) then

while true do { }

else

return false;

We will also define a machine “Loop If Halt On It Self” 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.

Function LoopIfHaltsOnItself (M):

return LoopIfHalts (M, M):

Finally, we ask what happens if we try:

Function Impossible:

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.