Problem Solving: Halting problem

Halting Problem

Very early on in modern computing, a British academic named Alan Turing devised the halting problem. This problem is to do with whether we can determine if a program will ever come to a halt or run for ever, for example:

console.writeline("hello")

Would write hello to the screen then stop. However, take a look at:

dim x as integer = 9
while x > 8
  console.writeline("hello")
end while

This would never finish, it would never come to a halt as x will always be larger than 8 and never get any smaller. This means the while loop will continue for ever, constantly printing out "hello". In the two cases shown it is easy to tell if a program will halt or not, but it isn't so easy for all programs. Imagine we get a more complex piece of code:

dim x as integer = 9
dim total as integer = 0
while total < 100
  total = total + x
  x = x / 2
end while

This is harder but still solvable taking a little more thinking and a little time on the processor. We could get a piece of code that takes weeks, years or even thousands of years to finish. But how can we know that all programs will end or not? To determine whether the program halts we:

• run a program with a given input, if it stops we know it stops
• BUT if it keeps running beyond a reasonable amount of time we cannot conclude that it will loop for ever (maybe we need to wait a little longer...)

Surely we create a mathematical proof to determine whether code will end or not I hear you say. Well let's prove just the opposite:

The halting solution H takes an input program A and a set of inputs X, it then determines whether the program will finish executing or not

You can replace the Input X with a copy of the program A. As the program A is made from code, this can be transformed into 1s and 0s, giving H a data input

Let us create a program K that will loop forever if the result of H is to halt, and halt if the result of H is to loop for ever:

function K(i):
    if H(i,i) = halt then
        loop forever
    else
        halt

If H says halt, K will loop. If H says loop K will halt, thus the Halting Solution H will be undecidable

We can therefore see that there are examples of programs such as K that we cannot determine whether they are ever going to halt.

• Read more on the halting problem