The Halting Problem

The halting problem is a classic problem in computer science that is frequently taught in undergraduate computer science curriculums. The problem concerns the feasibility of writing a computer program that can look at another arbitrary program and its inputs and determine if that program will terminate, or if instead it will run forever.

The classic proof for this problem (which was published by Alan Turing in 1936) uses a clever construction showing that if such a computer program existed it could be made to contradict itself. The proof is elegant and interestingly is analogous to (but much simpler than) the proof used by Kurt Gödel in his incompleteness theorems. While not actually a proof of the halting problem, I think that it’s worth considering the implications that a positive solution for the halting problem would have on some classic problems in mathematics, as this can help develop some further intuition. To be clear on the terminology here: a positive solution for the halting problem means that there is a program that can look at another program and its inputs and determine whether or not it halts.

One of the most famous problems in number theory is Fermat’s Last Theorem. The theorem was conjectured by Pierre de Fermat in 1637 and remained unproven, despite attempts at a proof by some of the greatest minds in mathematics, until Andrew Wiles published a proof in 1995. If there was, instead, a positive solution for the halting problem then it would be trivial to prove (or disprove) Fermat’s Last Theorem. We can easily write a program that enumerates through the space of all of the possibilities for a, b, c, and n since this is a countable set. Therefore, consider a program that enumerates this space and halts when it finds the first suitable set of values that would contradict Fermat’s Last Theorem. If Fermat’s Last Theorem is true then this program will never halt, and if Fermat’s Last Theorem is not true then the program will halt. Thus if we had a positive solution for the halting problem then we would also have a proof for Fermat’s Last Theorem.

The consideration for Fermat’s Last Theorem here is interesting because Fermat’s Last Theorem is known to be a difficult problem, but at the same time it has been proven so we know that in principle it’s possible to write a program that solves it. Consider instead Goldbach’s conjecture which is another famous problem in number theory, this one unproven (but widely assumed to be true). The conjecture states that every even integer greater than two can be expressed as the sum of two primes. We can easily write a program that checks if any number is prime and therefore we can also easily write a program that would check for a given even number if it is actually possible to express that number as the sum of two primes. Therefore we can write a program that runs until it finds the first counterexample for Goldbach’s conjecture. If there were a positive solution for the halting problem then Goldbach’s conjecture would be true if this program never halted, and would be false if it did halt. Therefore a positive solution for the halting problem would imply a trivial proof (or disproof) of Goldbach’s conjecture.

Another famous unproven problem in number theory is called the Collatz conjecture, which is also known as the 3n + 1 conjecture. This problem proposes a simple iterative method for transforming a starting natural number n into a sequence of other natural numbers. The conjecture posits that for all starting values of n the sequence will always converge to a short sequence containing the value 1. We can easily write a program that looks for counterexamples of the Collatz conjecture by writing a program that iterates on an input until it converges to a sequence containing the value 1, and then checking this program with our halting program. A positive solution for the halting problem would therefore imply a proof or disproof of this conjecture.

The examples I’ve given so far are easily demonstrated because they can all be disproven by finding a single enumerable counterexample. However, we can also fit some other more complex problems into this space. The twin prime conjecture posits that there are infinitely many prime numbers that differ by two; that is, there are infinitely many primes p where p + 2 is also prime. This conjecture is one of the oldest open questions in number theory and is widely assumed to be true. In fact, very recently (since 2013) a weaker version of the conjecture has been proven where it has been shown that there are infinitely many primes that differ by at most N; the current lower bound on N is 246. Either the twin prime conjecture is true, or it is not true in which case there is a finite number of twin primes. We can write a program that will exhaustively find the first k instances of twin primes. If there were a positive solution for the halting problem we could therefore test the twin prime conjecture by asking our halting program if the program finding the first k instances of twin primes halts for increasing values of k. In fact, for such a halting program to work (and be guaranteed to halt itself) for all inputs it would therefore be equivalent to proving the twin prime conjecture.

As you can see a positive solution for the halting problem would also imply immediate proofs for a large number of open, well studied problems in number theory concerning natural numbers. Therefore it shouldn’t be surprising that there is no solution for the halting problem. This argument isn’t the same as an actual proof—Alan Turing already did that in a rigorous manner—but I hope it helps you intuitively think about why a solution for the halting problem would be unlikely.