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.
