Computation – Halting Problem

Termination

Let’s take another look at the piece of simple Java code that we looked at earlier:

int sum = 0; int i = 0; while (i<n) { sum = sum + i; i = i + 1; }

It should be clear to you that this piece of code will terminate. For example, with this piece of code, the control variable, ‘i’ will start at the initial assignment of the value ‘0’, and then continue to increment on each loop until it reaches the value of ‘n’.  This will then terminate the while loop.

Let’s see another example of code:

while ( n != 1) { if (n/2*2 == n) { n = n/2; } else { n =  3*n+1; } }

Suppose ‘n’ has an initial value of 5. The while loop will successfully generate the following values of ‘n’:

16, 8, 4, 2, 1

That was easy! Suppose the initial value of ‘n’ is 9. We then have the following sequence of values:

28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

This program has tested the brains of many number theorists over the years. It is suspected that it will always terminate on initially positive numbers; however, as far as we’re aware, no proof has been found that it does indeed always terminate. Its termination remains an open problem.

Halting Problem

From the above examples, it is clear to see that it would be very useful if we could write a computer program, which would tell us whether computer programs will terminate on some given input.

Look at the image below; now let’s say that we have a program Q. This program has 2 inputs which are a program, Pand an input, X. Aside from this, it also has 2 output; yes and no. in other words, ‘yes’ program, P, terminates, and ‘no’ program, P, doesn’t terminates.

Such a program Q would be an excellent tool to possess. Unfortunately, we can prove that such a program Q can not exist, hence the Halting Problem.

This proof is by contradiction. First we assume that there is such a program, Q. With this we now construct another program called S. This program takes on input; Y. It makes a copy of ‘Y’ and calls the program ‘Q’ with pair inputs of ‘Y’ and ‘Y’. Now our assumption about the program Q is that it will eventually terminate with either a YES or a NO response. Program S then checks the response: if it is a YES answer, S then puts itself into an infinite loop; if it is a NO answer, the program S terminates. Clearly, assuming that program Q can be produced then the construction we’ve given will create a new program that terminates if the original input to program Q doesn’t terminate on the given input, but will loop infinitely for the other case.

We are now in a position to show that things don’t actually work. Program ‘S’ is just a program written in the language ’L’. Therefore, we can apply program ‘S’ to itself, i.e. pass in the text of program ‘S’ as input to itself. Let’s see what then happens. Program ‘S’ copies the text of itself and passes both as the input to the program ‘Q’. Now we’re asserting that the program ‘Q’ solves the halting problem and will therefore give an answer ‘YES’ is program ‘S’ terminates on the given input and ‘NO’ otherwise. Let us assume that ‘S’ does terminate, hence the program ‘Q’ will terminate with ‘YES’. This result will then cause program ‘S’ to go into a spin, i.e. loop infinitely, and therefore program ‘S’ doesn’t terminate. But this is in contradiction to the result we obtained from ‘Q’. If program ‘Q’ says that ‘S’ doesn’t terminate, lo and behold we have program ‘S’ terminating. Oh dear, there really is something wrong. Well, the crucial point is that we’ve been very careful in the construction of program ‘S’ in that the additional steps we’ve introduced to before calling and after calling program ‘Q’ are certainly programmable. We can therefore only conclude that the program ‘Q’ can not exist, which thus establishes that the Halting Problem is indeed not a decidable problem.