A conversation I had yesterday evening revealed something about computability and mathematics that hadn’t occurred to me. First, some preliminaries.

Consider a computer running a program written in a language with a finite number of symbols. The computer proceeds step by step through a string of instructions, some of which may tell it to execute commands from another location in the string of instructions. Some programs like this will run forever (for instance a program that simply enters an infinite loop) and others will do some finite number of things and then stop executing. Call these two groups of programs “non-halting” and “halting”, respectively. Defining these things suitably it is possible to prove that *if a program is halting, its length determines an upper bound on the number of steps it takes*. If the length of the program is n, call the maximum number of steps f(n).

Now consider a mathematical statement about the natural numbers, the unproved Goldbach’s conjecture for instance. The conjecture says that every even integer greater than 2 can be written as the sum of two primes. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 5+5, 60 = 7+53 etc. This is a claim about every even number there is, so presumably there isn’t any way to just do calculations to prove the conjecture: we have to prove it for all of the infinitely many even numbers at once.

Now consider a computer program that goes through even numbers, checking whether each can be written as the sum of two primes. This program is either halting or non-halting. If it is halting, Goldbach’s conjecture is false (because the program would only halt if it finds a counterexample). If Goldbach’s conjecture is true, the program is non-halting – but we can’t exactly wait forever to see that it never halts. But because we know that a program of length n will either halt by step f(n) or never, we only need to wait until the machine has taken f(n) steps. This means that *it is sufficient to do finitely many calculations to find out whether Goldbach’s conjecture is true*.

Unless I or the guy who explained this to me missed something; I haven’t actually read about this in a book or anything.

And of course this doesn’t make for a very feasible way to solve the problem because f(n) grows very quickly indeed.