← Feed
#Math #AI 19/n
One such example was the formalization, by Georges Gonthier,
of the proof by Appel and Haken of the four colour theorem.
This theorem says that if you draw a map on sheet of papers, with
as many countries as you wish (but countries need to consist
of only one piece, no islands nor colonies here), then it is possible
to draw countries with only four colours so that countries
sharing a common boundary have distinct colors.
The history of that theorem is really surprising. It was
proved in 19th century, but it took 10 years to observe that the given
proof was wrong. It was relatively easy to show that 5 colors indeed suffice,
and several new wrong proofs appeared in 20th century.
Only in 1976 did Appel and Haken propose a working proof, but
that proof used a computer program to enumerate a large number
of configurations, which another program could solve effectively,
the theorem being that this long list of examples was sufficient
to conclude.
Several problems arise at once: how can we be sure that
the first computer program actually generates all configurations
described by the mathematical theorem, and does not miss any,
and how can be be sure that all of them are treated correctly?
The list is so long that no single human, nor any small group
of humans, could check all of them, what we need is really
a third computer program that will certify the combination
of the mathematical proof, the configuration generator,
and the solution for each generated configuration.
Replies (1)
-
#Math #AI 20/n
This is what Georges Gonthier did in 2008, thus bringing
a definitive certainty to the solution of that long-standing
question. In fact, Gonthier discovered that the proof
didn't really work, but he could make the argument work.
I should (and will) ask Gonthier about his underlying motivation,
but my understanding is that, as one of the developers of
the proof assistant Coq (now named Rocq), he wished to prove the
mathematical community that the technology was mature enough
to tackle spectacularly long proofs. Another reason is that
Coq/Rocq is also the basis for a purely computer science activity
that is very close to checking mathematical proofs,
namely checking computer programs,
and this has applications in industry.
Open ##5153669