Halt!

You can’t work long in computer science until you have to understand the halting problem. The halting problem is concerned with determining whether a program will finish running or continue to run forever. It has a storied history. In 1936, Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. His proof was made famous since in this paper, he provided a mathematical definition of a computer and program, which became known as a Turing machine and the halting problem is undecidable over Turing machines and is one of the first examples of a decision problem.

Programmers generally try to avoid infinite loops—they want every subroutine to finish (halt). In particular, in hard real-time computing, programmers attempt to write subroutines that are not only guaranteed to finish (halt), but are guaranteed to finish before the given deadline.

But isn’t it easy to avoid infinite loops? Why is the halting problem so important? Because a lot of really practical problems are the halting problem in disguise. For example, say you want a compiler that finds the fastest possible machine code for a given program. You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can’t get at the high security information. This is also just the halting problem. Or, for example, if you have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. This is one more example of the halting problem. If you have an anti-virus program, and you want to see if it ever executes a malicious instruction, this is another example of the halting problem in action.

Moreover, the Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don’t exist, that sometimes, all we can do is guess at a problem, and never know if we’ve solved it. If we didn’t have the halting problem, we would still be searching for Hilbert’s magical algorithm which inputs theorems and outputs whether they’re true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.