Newtonpedia ES
Home › Computing › Computer-assisted proof
Computing · 1976

Computer-assisted proof

A mathematical proof that a computer has generated, at least in part, through lengthy calculations or automated checks.

Year
1976
Section
Computing

History

A computer-assisted proof is a mathematical proof in which a computer has played a part, at least partly, in generating or checking its steps. It matters because it extends what mathematicians can establish, while also raising a lasting question about what it means to truly prove something.

Before computers, proofs were written entirely by hand, through chains of logical reasoning that any mathematician could inspect. When a theorem requires checking a huge number of cases, the method of exhaustion means examining each case one by one. Doing this by hand was impractical, so the repetitive part of the work was handed to machines.

The most cited milestone came in 1976, when K. Appel and W. Haken proved the four colour theorem, which states that four colours suffice to colour any map so that neighbouring regions never share one. The question had been posed in 1852. The proof reduced maps to a finite set of configurations, and a computer checked each of them. It was the first major theorem verified with a computer program, and it provoked intense debate among those who expected a proof a person could follow by hand.

A second line of work, rooted in artificial intelligence, seeks new and shorter proofs built up from axioms using automated reasoning, such as heuristic search, which steers the search towards promising steps. These automated provers have produced genuinely new results and alternative proofs of known theorems. Interactive proof assistants, meanwhile, let mathematicians write proofs that people can read and that a machine then checks formally. Proofs of this kind, such as the proof of the Robbins conjecture, avoid much of the controversy surrounding exhaustive computer proofs, though even checking them by hand proved laborious.

A related technique is validated numerics, sometimes called rigorous numerics, which performs numerical calculations while controlling rounding errors. It relies on interval arithmetic: instead of a single approximate number, the computation carries an interval guaranteed to contain the true value, so the final answer is bounded with certainty.

Philosophical objections have been significant. Thomas Tymoczko was among the first to formulate them. He argued that a proof so long that no human can verify it step by step rests on trust in a computational process, which could be affected by software bugs, compiler faults or hardware defects. Other mathematicians reply that such work is really a calculation, and that the algorithm itself must be proved correct. Concerns about software are addressed by formal correctness proofs, as applied to the four colour theorem in 2005, and by reproducing results with different languages, compilers and machines. A further objection is aesthetic: these proofs often offer little insight or new concepts, though this complaint applies to any proof by exhaustion.

Today computer-assisted proofs are common in number theory, graph theory, nonlinear dynamics and optimisation. Notable examples include Kepler's conjecture, proved in 1998, the Robbins conjecture, settled in 1996 with program assistance, and the result that Rubik's Cube can always be solved in at most 20 face turns, in 2010. Their lasting impact is that they have changed how mathematical results are validated, and they have opened experimental mathematics, where numerical experiments help explore problems and suggest conjectures.

Timeline

  • 1852The four colour problem is posed.
  • 1976Appel and Haken prove the four colour theorem with computer assistance.
  • 1996The Robbins conjecture is resolved with the help of a computer program.
  • 1998Kepler's conjecture on optimal sphere packing is proved.
  • 2005A formal correctness proof is applied to the four colour theorem's program.
  • 2010It is shown that Rubik's Cube can be solved in at most 20 moves.

Trivia and anecdotes

Theorems for sale

In 2010, academics at the University of Edinburgh offered members of the public the chance to buy a theorem named after them, created through a computer-assisted proof.

A counterexample found by brute force

Euler conjectured that a fifth-power equation with four terms had no positive whole-number solution, yet a computer brute-force search found one, refuting the idea.

Other milestones in Computing