The halting problem describes why computers can't easily avoid crashing, or rather, why they can't predict when they are about to crash and avoid it. This entry is intended to be a reference point for every computer whiz who's been plagued by people asking why computers can't see a crash coming and stop it, but didn't know the full answer¹.

Turing Machines

A Turing machine is a simple computational device with an infinite length of 'tape' to store data on. The tape is split into a series of cells, like frames on a reel of film. It can move the tape forward or backward one cell at a time.

It was invented in 1936 by Alan Turing, who noticed that despite the machine's architectural simplicity it was an extremely powerful model of a computing device, and could be programmed to solve many problems. The Turing machine is a theoretical computer, which works by storing data on a tape of infinite length and moving back and forward along it according to the program. Even the program itself can be stored on the tape; these machines are called Universal Turing Machines.

Turing programs either halt when they have arrived at the results or else they continue forever. No Turing program can be said to have produced any results until it has halted.

The Halting Problem for Turing Machines

Turing asked himself whether it could be possible to write a program for a Turing machine which would solve the following problem:

Given (1) an arbitrary Turing machine, and (2) arbitrary input for the machine, will the given machine halt on the given input?

In other words, Turing wondered whether it would be possible to write a Turing machine program that would take two inputs:

1. A Turing machine program P, and
2. some input for program P

and would give as its output the answer to the question whether a Turing machine executing program P would ever halt on that input. The Turing machine is given program P and input i. It answers 'Yes' if the Turing machine would halt when executing program P on input i, and answers 'No' if it wouldn't halt (ie it would loop for ever - in effect, crash).

Turing's Wonderings

Turing wondered whether anyone could program a Turing machine to perform the computation described in the mathematical description above. He didn't think he personally could do it, but that didn't give him a definite answer, because maybe someone smarter could figure out how to do it, if they could construct a better program.

Turing realised, however, that he knew (in an abstract way) what all the possible Turing machine programs are. He knew that every possible Turing machine program has a description number, and that there aren't any more programs than there are description numbers, and there aren't any more description numbers than there are whole numbers².

Therefore, Turing realised that each whole number can be looked at as the description number of some Turing machine program, and no possible programs should be left out. So one way to figure out if there's a program that can solve the halting problem would be to look through all the whole numbers, interpreting each as the description number of a Turing machine program, and checking to see if it's the program that solves the halting problem.

Of course, this is completely impractical. But Turing realised that if he could prove that no whole number was the right one, then we'd know that no program to solve the halting problem exists.

The Proof

The proof proceeds by reductio ad absurdum³. We will assume that there is an algorithm Halt(a,i) that decides if the algorithm encoded by the string a will halt when given as input the string i, and then show that this leads to a contradiction.

Assume that algorithm Halt(a,i) returns the string 'yes' if the algorithm represented by the string a halts when given as input the string i, and returns the string 'no' otherwise. Given this algorithm we can construct another algorithm Trouble(s) as follows:

function Trouble ( s : string ) : string
begin

if Halt(s,s) = 'no'
then return('yes')
else ... some infinite loop ...
end

This algorithm takes a string s as its argument and runs the algorithm Halt, giving s both as the description of the algorithm to check and as the initial data to feed to that algorithm. If Halt outputs 'no', then Trouble outputs 'yes', otherwise Trouble goes into an infinite loop. Since all algorithms can be represented by strings there will be a string T that represents the algorithm Trouble. We can now ask the following question:

What is the output of Halt(T,T)?

We know by the definition of Halt that the output must be either 'yes' or 'no'. Let us consider both cases: Assume that the output is 'no'. Since Halt decides if the encoded algorithm halts for the given input, it follows that Trouble does not halt on input T. If we look at the algorithm of Trouble we can see that this is only the case if the result of Halt(T,T) is 'yes', which contradicts the assumption that the output is 'no'. Assume that the output is 'yes', then it follows by the definition of Halt that Trouble halts on input T. If we again look at the algorithm of Trouble we see that the result of Halt(T,T) then must be 'no', which contradicts the assumption that it is 'yes'. Since both cases lead to a contradiction there will always be a contradiction, and so the initial assumption, that the algorithm Halt exists, must be false.

Relationship with Gödel's Incompleteness Theorem

The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that a complete, consistent and sound axiomatisation of all statements about natural numbers is unachievable. The 'sound' part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers (it's very important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the question of truth, but only concerns the issue of provability).

Recognizing Partial Solutions

No program can solve the halting problem. There are programs that give correct answers for some instances of it, and run forever on all other instances. A program that returns answers for some instances of the halting problem might be called a partial halting solver. Can we recognise a correct partial halting solver when we see it? Let the partial halting solver recognition problem be this: given a partial halting solver, determine whether it returns only correct answers. This problem sounds like it might be easier than the halting problem itself. It is not. It is just as undecidable as the halting problem. This follows trivially from Rice's theorem. It also follows from the undecidability of the halting problem, as will now be shown.

For every instance of the halting problem, there is an instance of the partial halting solver recognition problem that is just as hard to solve. For example, the previous section showed an instance of the halting problem for which no one knows the answer. Here is how it can be converted into an instance of the partial halting solver recognition problem for which no one knows the answer:

Input a program P
If P = "for(i=j=k=1;--j||k;k=j?i%j?k:k-j:(j=i+=2));"
Output "Yes, that program halts"
else
loop forever

Does that program return only correct answers? No-one knows. This shows further just how difficult the halting problem is. There is no way to solve it in general. There isn't even a general way to know whether a program partially solves it.

University Course

The halting problem forms part of most computer science degrees. The course title is usually 'Computability & Complexity', but most of the students call it 'That Awkward Course With The Horrible Maths' because of the maths involved.

The course basically answers the question: Why can't a computer know when it's about to crash and prevent it? The answer is explained through the Turing Halting problem; there's no way to know what a program will do without actually running it.

The most general statement of the problem of self-prediction is that a predicting machine may not predict its own future internal states because in order to do so it would have to contain as part of itself a complete model of itself.

A Solution?

While it is true that the halting problem is currently one of the unsolvable problems in computing, there is also the possibility that in the future it won't matter.

There are plenty of mathematical problems where the program is doing exactly what it is supposed to do, but the program will never halt. For example, asking the program to keep going until it finds an odd number which is equal to the sum of its divisors. The program may halt when it finds one, or it may never halt, even though it is working perfectly. We have no way of knowing, because it is not known whether such a number exists. No program can know what the code will do without executing it.

However, some halting problems are caused by code errors, which are also governed by the same problem; you cannot know what the code will do without executing it. There is a field of computing which deals with proving the correctness of programs. This already allows us, with very small programs, to prove which parts of the program are known to have no common halting errors in them. While this doesn't prove that the program has no errors, it does provide extra levels of debugging based solely on the program's structure. Using this technique for small sections of code over the whole program, it is possible to create a probability that the program will terminate correctly. In the future, the CPU of the computer could pre-analyse the code before running it. If the probability is below a certain limit, the computer CPU can refuse to run the program, or can choose to analyse it further⁴.

Similarly, there are programmer tools which can give a 'reachability' graph for a given program and these can also help massively with debugging. So while the halting problem is currently viewed as being unsolvable, there are now lots of tools appearing which can be used to make it a lot less relevant most of the time.

The most commonly-used solution is to recognise when a program has stopped responding to input and terminate the program. However this is not full proof because the crash may bring the operating system down with it.