# Problem Solving: Halting problem

## Halting Problem

[edit | edit source]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:

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
```

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