Sunday, September 30, 2012

Can humans solve the halting problem?

In Wikipedia's article on the halting problem, there used to be a section called "Can humans solve the halting problem?" but I just noticed that it was deleted in 2008. There was minimal discussion about this deletion after it happened, and I would have voiced my opinion to keep the section had I noticed. However, instead of going through the necessary steps to reintroduce the content, I will just paste (most) of the section here.

Can humans solve the halting problem?
It might seem like humans could solve the halting problem. After all, a programmer can often look at a program and tell whether it will halt. It is useful to understand why this cannot be true. For simplicity, we will consider the halting problem for programs with no input, which is also undecidable.

To "solve" the halting problem means to be able to look at ''any'' program and tell whether it halts. It is not enough to be able to look at ''some'' programs and decide. Even for simple programs, it isn't clear that humans can always tell whether they halt. For example, we might ask if this pseudocode function, which corresponds to a particular Turing machine, ever halts:

function searchForOddPerfectNumber()
  var int n = 1    // arbitrary-precision integer
  loop {
    var int sumOfFactors = 0
    for factor from 1 to n - 1 {
      if factor is a factor of n then
        sumOfFactors = sumOfFactors + factor
    if sumOfFactors = n then
      exit loop
    n = n + 2

This program searches until it finds an odd perfect number, then halts. It halts if and only if such a number exists, which is a major open question in mathematics. So, after centuries of work, mathematicians have yet to discover whether a simple, ten-line program halts. This makes it difficult to see how humans could solve the halting problem.

More generally, it's usually easy to see how to write a simple brute-force search program that looks for counterexamples to any particular conjecture in number theory; if the program finds a counterexample, it stops and prints out the counterexample, and otherwise it keeps searching forever.  For example, consider the famous (and still unsolved) twin prime conjecture. This asks whether there are arbitrarily large prime numbers p and q with p+2 = q.  Now consider the following program, which accepts an input N:

function findTwinPrimeAbove(int N)
  int p = N
    if p is prime and p + 2 is prime then
      p = p + 1

This program searches for twin primes p and p+2 both at least as large as N.  If there are arbitrarily large twin primes, it will halt for all possible inputs.  But if there is a largest pair of twin primes P and P+2, then the program will never halt if it is given an input N larger than P.  Thus if we could answer the question of whether this program halts on all inputs, we would have the long-sought answer to the twin prime conjecture.   It's similarly straightforward to write programs which halt depending on the truth or falsehood for many other conjectures of number theory.


  1. I don't think this argument works.

    What you've done is to show that, for a human to solve the halting problem, he'd have to be able to solve those other problems -- but you haven't shown that humans *can't* solve them, only that they haven't.

    You'd have to tie it to something that we know humans *can't* solve -- but then you'd have to show a program that solves it and ask whether *that* halts.

  2. Yes, of course you are right. That is why the Church-Turing Thesis is just that, a thesis, not a theorem. The argument above is for those that think humans are "clearly" smarter/better than computers. The point here is that this is in no way "clearly" true.

  3. I thought the same thing after learning about the halting problem, and your article is the first satisfactory answer I've come across. Very good examples.

  4. (Coming reeeeaaaally late to this but better late than never :)
    The issue I find with your argument is that it involves human non-omniscient.
    However the halting problem is deeper than that in the sense that even if we were to grant someone omniscience (e.g. suppose we are talking about Laplace's demon) he/she would still be unable to decide all problems.
    So even if one knows the answer to any conjecture conceivable they would still be unable to, say, enumerate the real numbers.

    The halting problem has nothing to do with human limitations but rather with the nature of nature itself.

    Of course your argument works quite nicely to demonstrate to someone who does not want to bother with diagonilization arguments and so forth and they just claim that humans are more clever than computers (without assuming that humans are all omniscient though)

    My question to such a person though would be "how on earth an animal such as the homo sapiens differs from a Turing machine."