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