Automatic Theorem Proving

To Microsoft Research in Cambridge on Thursday, to hear Prof Sir Timothy Gowers lecturing on What are the Prospects for Automatic Theorem Proving?.

An example of the English academic at his best: self-deprecatory, cautious, but absolutely certain when on his own ground. Above all, able to explain a complex subject in a way which a non-specialist could understand.

He is trying to design a theorem proving system which mimics human judgement rather than relying on massive brute force attacks, and as a teacher he is in an excellent position to see how mathematical judgement develops in humans.

His system works by
– stating the problem clearly in terms the system can understand (he is working to use natural language as much as possible)
– having a list of heuristics (something like the list in Polya’s book ‘How to Solve It’, I assume, though perhaps more sophisticated.)
– assessing the problem and assigning probabilities to each heuristic: which is most likely to solve the problem? (This is easier said that done, of course!)
– applying the selecting heuristics until a solution is found. (How does the system know a solution has been found?)
– displaying the answer, again in a mixture of mathematical notation and natural language.

It would be an exciting system if it worked, and might well generate a lot of new proofs. (You could set several machines running, and forget about them.) According to Wikipedia, automatic systems have already proved at least one theorem which had defied human efforts, the Robbins Conjecture.

I find myself wondering how Goedel’s incompleteness theorems fit in. Suppose Prof Gowers invents a perfect theorem prover: according to Goedel, there ought to be some theorems that even this machine cannot prove. Of course it should still be able to prove a great many, but if it ran up against an unprovable theorem, it might be interesting to see why it could not succeed, and if there was any common theme.

Reminds me of the section in Toby Segaran’s book ‘Collective Intelligence’ on automatically evolving programmes, eg to generate equations which relate sets of numbers, or to play a simple game. He uses more of a ‘random forest’ technique, evolving each programme as a tree built from a small set of operations (add, multiply, etc), which are randomly selected using a genetic model – ie randomly make a generation, select the best, modify them slightly, select the best, and so on, and sometimes combine elements of two successful programmes to make a third, select the best, etc etc. Of course finding an equation that produces the right result is not the same as proving a conjecture or theorem, but the same issues seem to arise: for example the machine-made equations are often far more complex and repetitious than they need be, and need to be simplified by hand.

Leave a Reply

Your email address will not be published. Required fields are marked *