Nqthm

Nqthm is a theorem prover sometimes referred to as the Boyer–Moore theorem prover. It was a precursor to ACL2.

The system was developed by Robert S. Boyer and J Strother Moore, professors of computer science at the University of Texas, Austin. They began work on the system in 1971 in Edinburgh, Scotland. Their goal was to make a fully automatic, logic-based theorem prover. They used a variant of Pure LISP as the working logic.

Definitions are formed as totally recursive functions, the system makes extensive use of rewriting and an induction heuristic that is used when rewriting and something that they called symbolic evaluation fails.

The system was built on top of Lisp and had some very basic knowledge in what was called "Ground-zero", the state of the machine after bootstrapping it onto a Common Lisp implementation.

This is an example of the proof of a simple arithmetic theorem. The function TIMES is part of the BOOT-STRAP (called a "satellite") and is defined to be

The formulation of the theorem is also given in a Lisp-like syntax:

Should the theorem prove to be true, it will be added to the knowledge basis of the system and can be used as a rewrite rule for future proofs.

The proof itself is given in a quasi-natural language manner. The authors randomly choose typical mathematical phrases for embedding the steps in the mathematical proof, which does actually make the proofs quite readable. There are macros for LaTeX that can transform the Lisp structure into more or less readable mathematical language.

The proof of the commutativity of times continues:

and after winding itself through a number of induction proofs, finally concludes that

...
Wikipedia