logoalt Hacker News

wodenokoto • yesterday at 10:56 AM • 12 replies • view on HN

Isn’t “proof is checked in Lean” kinda similar to assuming your code works just because it compiles.

Sure, the code works, but does it work at doing what you want?

Sure, the proof is valid, but does it prove what you set out to prove?


Replies

throwawayffffas • yesterday at 12:44 PM

The gist of the article is that it's worse.

That it's the equivalent of saying "It's full moon tonight because I wrote this program".

And he states that you have to check that:

1. The statement the author is making corresponds to the statement in the lean program.

2. The lean program actually compiles.

3. There is no shenanigans hidden in the lean program to disguise a trivial proof as the one stated.

4. The program does not exploit bugs in lean.

➕ show 4 replies
program_whiz • yesterday at 1:15 PM

Reading the friendly article:

It is worth noting that of the 290 OpenAI theorems which come with Lean code, around 38 of them have the property that the Lean code does not even state, let alone prove, the main theorem of the paper.

So even if LEAN is 100% bug-free, its still on the programmer to correctly express the logic and proofs, or they could be proving completely unrelated facts.

➕ show 2 replies
fancyfredbot • yesterday at 11:57 AM

I think it's a reasonable point but a bad analogy.

It's more like assuming that because your code is formally proven correct the client will be happy with it.

The code can be right but it may still do the wrong thing.

➕ show 1 reply
Gabriel54 • yesterday at 2:15 PM

For relatively "simple" statements in mathematics it is pretty easy to learn enough Lean to verify that the Lean statement correctly encodes the intention of the mathematics. It gets more difficult in certain areas of mathematics where there are many layers of definitions and they haven't been standardized in Lean yet.

bananaflag • yesterday at 11:36 AM

No, because proofs are programs and theorems are types. It is enough to construct a function of the needed type to have a proof of the needed theorem. You don't need to look through all the code to see that the function has the desired type.

➕ show 4 replies
yk • yesterday at 1:26 PM

On a technical level, yes. Though lean is build such that "it compiles" is a very strong statement about mathematics while most programming languages are not build to provide a very strong statement about correctness of the program. It is perhaps more similar to checking an equation numerically.

paulpauper • yesterday at 9:05 PM

The burden of proof is way higher for lean compared to software. Software only has to work for the end user. A mathematical statement must be exact.

paulddraper • yesterday at 3:20 PM

Yes it’s a good analogy.

You have to watch out for

1. Translation. Do the author’s claims about the program/theorem match the actual code?

2. Do you employ “shenanigans” to circumvent the checker? Bugs, unsafe operations. — Lean is a very strict checker as compilers go. Some compilers intentionally say “buyer beware.” It’s annoying to check for integer overflow in every operation. Lean doesn’t. But that still doesn’t mean it has zero bugs, in the framework or axioms.

oulipo • yesterday at 11:05 AM

If the proof is valid, it DOES prove what your theorem is saying (except for rare verification kernel bugs). The issue is mostly: did you correctly formalize and check the specification of your theorem itself...

dgellow • yesterday at 12:16 PM

I mean, in some strange way, yes. Because your type system is basically a set of claims that are proven by your compiler. But the analogy doesn’t go further than that. The running program itself is the proof

j16sdiz • yesterday at 11:23 AM

it is more like "unit test pass"

Fresh today, I asked llm to fix a unit test for me, it replaced the test with no-op.

➕ show 1 reply