10 - Automated Theorem Proving

Summary

in the early seventies, when word of Martin-Löf's type theory and subsequent research on the subject had not yet reached computer scientists, the idea that a proof is not built solely with axioms and inference rules but also with computation rules developed in computer science – especially in a branch called “automated theorem proving.” Thus, work on type theory and work on automated theorem proving were pursued contemporaneously by two distinct schools that ignored each other – admittedly, an improvement on the behavior of the schools that developed, respectively, the theory of computability and the theory of constructivity, which abused each other. It was not until much later that the links between these projects were finally revealed.

An automated theorem proving program is a computer program that, given a collection of axioms and a proposition, searches for a proof of this proposition using these axioms.

Of course, Church's theorem sets a limit on this project from the outset, because it is impossible for a program to decide whether the proposition that it has been requested to supply with a proof actually has one or not. However, there is nothing to prevent a program from searching for a proof, halting if it finds one, and continuing to look as long as it does not.

THE FANTASY OF “INTELLIGENT MACHINES”

In 1957, during one of the first conferences held about automated theorem proving, the pioneers in the field made some extravagant claims. First, within ten years, computers would be better than humans at constructing proofs and, as a consequence, mathematicians would all be thrown out of work. Second, endowed with the ability to build demonstrations, computers would become “intelligent”: they would soon surpass humans at chess, poetry, foreign languages, you name it. Cheap sci-fi novels began to depict a world in which computers far more intelligent than humans ruthlessly enslaved them. Ten years went by and everyone had to face the facts: neither of these prophecies were even close to being fulfilled.