3.1.5- The Halting Problem

Section 1.5: Intractable problems

The Halting Problem

It is not possible to write a program that is able to take any other program and say if that program will halt or not.

When you run a program, it will do one of two things:

        It will run for a while and then halt (stop).

        It will run forever (i.e. it will never halt).

The second of these is not usually a good thing – you would normally want your program to terminate.

Explanation

It is fairly easy to tell that the second program will not terminate as it is a fairly simple program. Most programs are far more complex and you cannot tell by just looking at the code if it will terminate or not.

One way of trying to find out if a program terminates or not is to run the program and see. If the program stops running after a while, you know that the program does terminate. 

The problem with this though is that if the program has not terminated you have no way of knowing if the program does not terminate, or if it has just not terminated yet (if you leave it running for another second it may terminate).

Alan Turing – proof by contradiction

It would be useful if there was a program that could tell you if any program you have written will terminate.

In the 1930s Alan Turing proved that no such program could exist. To show this he used proof by contradiction.

In proof by contradiction you assume that something is true and then show that this results in a contradiction proving it to be false

Example

A program called halt that takes a program as an input and then outputs whether the program can halt or not.

                Halt(program)

                                If program halts then

                                                Return true

                                Else

                                                Return false

The question is whether it is possible to write the program halt? Remembering that it should be able to take any program and say if it halts or not. Therefore, if we find one program that it doesn’t work for then we have proved that it cannot exist.

A new program can be written called contradict which takes a program as a parameter and makes use of halt as a subroutine.

                Contradict(program)

                                If halt(program) returns true then

                                                X = 0

                                                While x<1                           

                                                End while

                                If halt(program) returns False then

                                End

ßif the program reaches the while loop it will get stuck in an infinite loop as x will always be less than 1. If a program enters an infinite loop it doesn’t halt

If when contradict is given itself as a parameter to itself and contradict terminates then halt(contradict) will return true, this means that it will then execute the infinite loop, getting stuck in the process. This is turn means that the program contradict  does not terminate. Which contradicts what was said earlier.

If however contradict does not terminate then halt returns false and the program contradict will then stop running, which means that contradict does terminate which contradicts what was said earlier.

Conclusion

We can now see that if contradict does terminate then it doesn’t. But if it says that it doesn’t then it does.

This isn’t possible and therefore the assumption that it is possible to write the program halt that can take any program and say whether it terminates is false.

It can now be seen that the halting program is uncomputable- it’s not possible to write a program that can tell if any program will halt or not.