News for hackers. Stuff that matters.
Re:CompCert: A formally verified optimizing C compiler by arcatek on Monday March 02, 2015 @05:03AM (#9131148)
In science it may happen because everything is based on a lot of assumptions, themselves based on our physical perception of the world, which may be proved wrong later in time.

Are mathematics subject to this kind of flaws ? There is a very restricted set of axioms, and almost everything else is based on formal proofs.

Re:CompCert: A formally verified optimizing C compiler by one-more-minute on Monday March 02, 2015 @05:20AM (#9131194)
Re:CompCert: A formally verified optimizing C compiler by lmm on Monday March 02, 2015 @06:44AM (#9131401)
Wiles' proof was not written in machine-checkable language; if it had been, the error would almost certainly have been caught.
Re:CompCert: A formally verified optimizing C compiler by ngrilly on Monday March 02, 2015 @03:24PM (#9134093)
According to my very fresh reading on this topic, you are right, but your comment give the impression that writing Wile's proof in a machine-checkable language is not very different from writing it in a human language.

According to this article, I understand it is a lot more difficult to write a proof in a machine-checkable language, in the current state of the art:

http://www.cs.rug.nl/~wim/fermat/wilesEnglish.html

I read a lot of comments on Hacker News and Lobsters saying "you could have avoided this bug by writing your program in Idris, Coq, Haskell, etc. and enjoying the benefits of the Curry-Howard Isomorphism". But I'm under the impression that most of this comments undervalue the effort in "feeding" the type/proof checker with the necessary formalism.

I'm not saying that establishing a proof is worthless. Of course there is a lot of value in having a formal proof. I'm just saying that even for full-time professional mathematicians, machine-checkable formal proofs are still the exception, not the norm. This suggests the cost of building these proofs is still high, and it may explain why the practice is still limited in the field of computer science.

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Monday March 02, 2015 @09:08AM (#9131882)
But writing Wile's proof in a machine-checkable language wouldn't have been a problem in itself?

There is no "universal" machine-checkable language which can be used for any proof. I don't know if Wiles' proof could have been written in Coq, for example. Let's say it can't, and that no existing machine-checkable language can be used for this purpose. In such a case, you would have to develop a new proof language, and make sure the proof checker itself is correct.

I guess that at some point we are hitting the theoretical limits imposed by the halting problem and Gödel's incompleteness theorems?

It's not my field so I'm just asking questions here. Don't hesitate to lecture me :-)

Re:CompCert: A formally verified optimizing C compiler by thoran on Monday March 02, 2015 @09:46AM (#9132020)
No, you're wrong. This is not a theoretical issue there, but a practical one.

Almost all mathematics (and this certainly includes Wile's proof) could be written in Coq, in theory. It is extremely hard to do in practice.

Mathematicians write proof for their peers who have a smart brain. Most of the trivial and less than trivial details are omitted. Coq cannot not accept this (because he is very stupid and can't figure the missing steps). It turns out that it is particularly hard and boring to fill the missing holes in a "human" proof.

Gödel comes in when you try to prove Coq's correctness within Coq (but this was partially done, in a sense)

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Monday March 02, 2015 @03:09PM (#9134012)
I want to make sure I understand correctly. :)

I am right on the fact that rewriting Wile's proof in a machine-checkable language is a problem in itself? But I'm wrong when I suggest it is theoretical issue, when it's actually practical issue?

I've read that "the theory behind Coq is generally admitted to be consistent with regard to Zermelo-Fraenkel set theory + inaccessible cardinals". [1] I also read that some statements are undecidable in Zermelo–Fraenkel set theory [2]. It follows from this that it must exist some statements that are undecidable in Coq, correct? But I understand that this is theoretical issue, not a practical one, because "Zermelo–Fraenkel set theory, combined with first-order logic, gives a satisfactory and generally accepted formalism for essentially all current mathematics". Is it the reason why my comment was wrong?

On this topic, I've read an article titled "Computer verification of Wiles' proof of Fermat's Last Theorem" which explains that Wile's proof could probably be verified with a tool like Coq, but that would be a massive challenge:

> The mathematics used in Wiles' proof of Fermat's Last Theorem is very complicated. [...] I do not know the provers Coq and Mizar good enough, but I think they are adequate to express the mathematics.

> On the other hand, I do think that the challenge is doable, and that it will be done in the coming fifty years. It is definitely not within reach. The project will have to cover large parts of current pure mathematics. Its scope is comparable with the Bourbaki project, where between 1950 and 1970 almost all of pure mathematics got a new foundation by the efforts of an originally French group of mathematicians who published some 20 books under the pseudonym N. Bourbaki.

[1] https://coq.inria.fr/faq [2] http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_th... [3] http://en.wikipedia.org/wiki/Hilbert%27s_program [4] http://www.cs.rug.nl/~wim/fermat/wilesEnglish.html

Re:CompCert: A formally verified optimizing C compiler by thoran on Monday March 02, 2015 @05:13PM (#9134705)
It's my fault, I think I read your answer too quickly and miss a negation somewhere.

So, yes, a formal rewriting of Wiles' proof is "only" a practical challenge. But a big one. Just about 15 years ago, we were just able to prove the Fundamental theorem of algebra in Coq (a 200 years old theorem that is routinely taught to undergraduates).

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Tuesday March 03, 2015 @03:20PM (#9140411)
That's okay @thoran! Thanks a lot for having helped me gaining a better understanding of this topic.
Re:CompCert: A formally verified optimizing C compiler by lmm on Monday March 02, 2015 @03:21PM (#9134077)
> It follows from this that it must exist some statements that are undecidable in Coq, correct?

Yes, but only those that are undecidable in ordinary mathematics. If you're not using Coq, you have exactly the same problem. (And this concern doesn't apply if we already have the proof and just want to check it).

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Monday March 02, 2015 @05:16PM (#9134724)
> Yes, but only those that are undecidable in ordinary mathematics. If you're not using Coq, you have exactly the same problem.

Yes, this is what I understood. Thanks for confirming this point.

> (And this concern doesn't apply if we already have the proof and just want to check it).

Why this concern would not apply anymore if we already have the proof and just want to check it? The proof still needs to be expressed, directly or indirectly, in terms of Zermelo–Fraenkel set theory combined with first-order logic. If the proof uses a different and "incompatible" theory, how could we check it with Coq?

(I understand this is a very rare occurence in practice and this is the reason why ZFC is so much used.)

Re:CompCert: A formally verified optimizing C compiler by lmm on Tuesday March 03, 2015 @02:07AM (#9136475)
> The proof still needs to be expressed, directly or indirectly, in terms of Zermelo–Fraenkel set theory combined with first-order logic. If the proof uses a different and "incompatible" theory, how could we check it with Coq?

If Wiles' proof wasn't in ZFC we wouldn't call it a proof (at least not without qualification). You don't get to just write mathematical proofs in any language you like - otherwise we could pick a language in which FLT is an axiom, and then the proof of it is trivial.

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Tuesday March 03, 2015 @04:20PM (#9140847)
I don't get it. There is a lot of variants of set theory. ZFC is just one of them, albeit the most common. But some proofs are founded on an extension of ZFC. For example, the Mizar system, which is another proof assistant, has adopted Tarski–Grothendieck set theory, an extension of ZFC.

According to "The QED Manifesto Revisited" [1], it can be difficult to use Coq as-is for some kind of proofs:

> Here are four mathematical statements that most mathematicians will consider to be totally non-problematic: [...] We claim that currently none of the QED-like systems can express all four statements in a good way. Of course one can easily extend the systems with axioms that allow one to write down these statements. However, that really amounts to ‘changing the system’. It would mean that both the library and the automation of the system will not be very useful anymore. Classical & extensional reasoning in Coq or abstract algebra in the HOLs by postulating the necessary types and axioms will not be pleasant without re-engineering the system.

[1] http://mizar.org/trybulec65/8.pdf

Re:CompCert: A formally verified optimizing C compiler by lmm on Wednesday March 04, 2015 @09:57AM (#9144537)
> I don't get it. There is a lot of variants of set theory. ZFC is just one of them, albeit the most common. But some proofs are founded on an extension of ZFC. For example, the Mizar system, which is another proof assistant, has adopted Tarski–Grothendieck set theory, an extension of ZFC.

Some mathematicians accept extensions of ZFC. But I would definitely expect a proof that relied on such an extension to have in big red letters "we use these additional axioms", and the mathematical community would hope for and expect a proof without it. (Indeed proofs that make use of the axiom of choice still often flag this up and we look for proofs without it where possible). I am quite surprised that Mizar would do this, and certainly hope that it provides a way to distinguish between proofs that are valid in ZFC and those that aren't.

> According to "The QED Manifesto Revisited" [1], it can be difficult to use Coq as-is for some kind of proofs:

The statement about aleph-0 and aleph-2 (the one that Coq has problems with) isn't really mathematics so much as metamathematics/proof theory, at least if we're viewing it as a statement about the consequences of axioms. Which sure is a valuable field and one we'd like to be able to reason about, but it's circumscribed and doesn't affect normal working mathematics.

If we're talking about accepting that axiom and actually using it in a proof, then it's certainly not "totally non-problematic". The paper admits that most mathematicians wouldn't even know the statement of the proper forcing axiom. They certainly wouldn't write proofs that depended on it.

Re:CompCert: A formally verified optimizing C compiler by ngrilly on Wednesday March 04, 2015 @01:31PM (#9146283)
Thanks a lot @lmm. Now I get it :)

About Mizar, I don't know if you can use it without the additional axioms of Tarski-Grothendieck set theory.

Re:CompCert: A formally verified optimizing C compiler by Drakim on Monday March 02, 2015 @05:07AM (#9131161)
Surely the implementation of the mathematics may be subject to errors, just like any implementation of anything? There is nothing that is so perfect that humans cannot err while applying it.
Re:CompCert: A formally verified optimizing C compiler by scscsc on Monday March 02, 2015 @05:21AM (#9131197)
It is true that there might be errors in anything.

However, this is mitigated by having only a very small core that checks the proofs. Basically if there if a wrong proof goes through, there must be an error in the core (which was checked by many people and is very small).

Re:CompCert: A formally verified optimizing C compiler by vertex-four on Monday March 02, 2015 @07:19AM (#9131490)
You have to translate between the English spec and the computer-readable proof, and surely it's relatively easy to mess that up in some way and end up proving the wrong thing.
Re:CompCert: A formally verified optimizing C compiler by qznc on Monday March 02, 2015 @07:50AM (#9131561)
The C spec and x86 assembly are two very well known specs.
Re:CompCert: A formally verified optimizing C compiler by vertex-four on Monday March 02, 2015 @09:13AM (#9131897)
If they're very well known and everyone can understand them and implement them perfectly, we wouldn't need formal verification in the first place.

I don't doubt that formal verification significantly reduces the chances of bugs, but it's not a panacea, or we have computers that read our minds. You still need to verify that the proof is proving the right thing, although you can be sure that it's internally consistent.

Re:CompCert: A formally verified optimizing C compiler by more_original on Monday March 02, 2015 @04:36PM (#9134495)
> If they're very well known and everyone can understand them and implement them perfectly, we wouldn't need formal verification in the first place.

We're verifying the compiler from one language to the other. The specifications of the two languages are not that hard to implement. The difficulty is covering all cases in compiling from one to the other. The formal proof does tell us that we haven't missed any.

Re:CompCert: A formally verified optimizing C compiler by Drakim on Monday March 02, 2015 @07:47AM (#9131554)
I agree that the chances are pretty small, but is that "good enough" when it comes to formally verifying things?

(I know next to nothing about formal verification)

Re:CompCert: A formally verified optimizing C compiler by scscsc on Monday March 02, 2015 @11:40AM (#9132703)
Well, that's also true.

But apparently there is no better thing to do.

There is always a disconnect between what you mean and what you say. It happens all the time and the risk is not going to go away. People who work with proof assistants understand this risk better and most of them are pretty happy that the risk is sufficiently small for their purposes.