5 ms·
I know there has been a lot of work in automated theorem proving. I'm curious if anyone here is able to describe the state of the art in that. Is it really jus
by crazygringo 9y ago
I know there has been a lot of work in automated theorem proving.
I'm curious if anyone here is able to describe the state of the art in that. Is it really just a toy for basic things right now, or how realistic is it that we'd ever get to a point where the author of a paper like this could use a formal language to show that their proof is indeed valid and complete?
- LeanderK 9y agoI am not an expert, but I recently took a course on formal systems, which included theorem proving. It was more focused on proving properties for code since this is the focus of my professor, but I was really surprised how well it was working. I also recently tried out Liquid-Haskell, which adds an SMT solver (i think...) to Haskell. In my opinion, theorem proving has come a long way and I think the challenge is now equal in theorem-proving and programming language. We have to get the ergonomics right, deriving properties for imperative code is awful. We need a super elegant, easy to use and not too restrictive language that can be verified automatically. The overhead of using it must be minimal.
- smaddox 9y ago[Idris](https://en.wikipedia.org/wiki/Idris_(programming_language) https://en.wikipedia.org/wiki/Idris_(programming_language)) looks promising for theorem proving. I'm not sure I would say the overhead of using it is minimal, but it's at least a very expressive language.
- xvilka 9y agoThere is Agda, which was created for that, and even HoTT has a formalization in this language.
- sanxiyn 9y agoIt is realistic in the sense that it has already been done! But it's still laborious in the extreme. Kepler conjecture was stated in 1611 and had been unsolved since. Thomas Hales started a project to attack it in 1992. After six years of work, he announced the proof in 1998, in the form of 250 pages of argument and 3 gigabytes of computer calculation. He submitted it to Annals of Mathematics, one of the most prestigious math journal, for review. Reviewers and the author tried valiantly for five years, gave up, and published it in 2003 with a warning that while reviewers were 99% certain, it couldn't be completely reviewed. Soon after getting this both rejection and acceptance, Thomas Hales announced the plan to formalize his proof to remove any uncertainty. It was enthusiastically received by automated theorem proving community. For a while Thomas Hales "shopped" for the prover tool to use and basically leaders of every significant provers tried to "sell" it to him. He decided on HOL Light, wrote the detailed plan for formalization, and estimated it would take 20 years. He actually carried out this plan, announced the completion in 2014, wrote the paper on formalization, and submitted the formalization paper, with 21 collaborators, in 2015. The formalization paper was published in 2017. So there's that. The formal proof of Kepler conjecture is at the moment the most significant corpus of formalized mathematics in existence.
- chii 9y ago> After six years of work, he announced the proof in 1998 then > plan to formalize his proof ... estimated it would take 20 years so is it just me, or is the "work" of the normal proof only took 1/5th of the time it took for the automated/formalized proof?! that seems counter-productive imho...
- seanmcdirmid 9y ago21 collaborators. Depending on how much time they each spent on it, he could have easily gone over budget. Also, as it was all unknown stuff at the time, any estimation would have been made without prior experience.
- alexbeloi 9y agoHow does that compare to the time it takes to write code vs test code? Maybe not quite that extreme, but test code is time consuming, and is essentially what theorem proving is.
- umanwizard 9y agoHow is test code related to theorem proving?
- yoha 9y ago"Automated proof" means that the verification is automated. Actually automating the process of finding proofs is still mostly an open problem. Formal proof software will help you on small stuff, but you will still do most of the work, and you have to go much more in details, so it takes much more time.
- aurelianito 9y ago> so is it just me, or is the "work" of the normal proof only took 1/5th of the time it took for the automated/formalized proof?! that seems counter-productive imho... It took 5 times to make it not a hunch but a real demonstration. If that's counterproductive or not remains as a something opinable.
- seanwilson 9y agoIt's still a significant order of magnitude more time consuming to write a formal proof as you can't gloss over any details. Proof automation helps somewhat but the search space is so enormous it's not going to be feasible any time soon that you can avoid doing the difficult parts yourself. The formal proof for the Kepler conjecture involved around 15 people and was estimated to take around 20 years of work I think. If the summary for this proof is 300 pages, the formal proof would probably be 3K pages at least.
- anewhnaccount2 9y agoBy the way, if anyone is interested in getting a feel of the difference between these types of systems but is more just generally interested and doesn't necessarily have anything they want/need to prove themselves this: http://www.cs.ru.nl/~freek/comparison/comparison.pdf http://www.cs.ru.nl/~freek/comparison/comparison.pdf is a good document to skim through/jump around.
- c-cube 9y agoSo, there are two main areas of development in the automation of theorem proving. The first one is proof assistants, such as Isabelle/HOL, HOL Light, HOL4, Coq, PVS, Lean, TLApm (and others). These are typically languages to be used directly by a human, and share many common features with programming languages. In a sense, you "program" your proof. There are some large developments in such languages, as pointed out in other comments, including the Kepler conjecture (in HOL Light), the 4 colors theorem and Feit-Thompson theorem (in Coq), a fully verified micro-kernel (SEL4, in Isabelle/HOL), etc. It's an active research area with multiple teams around the world, but the provers are still difficult to use for non-experts. Isabelle/HOL has some nice features and good documentation that make it a bit more approachable to newcomers, afaik, and Lean has promising design decisions, but clearly right now it's a lot of effort to formalize anything consequent in proof assistants. The second area is fully automatic provers — an endeavour started very early (50s, 60s?). Such provers accept a logic formula as input, and try to compute if it's a theorem or not. They typically accept more restricted fragments of logic (because it's a super hard problem!). Even first-order logic, which is less expressive (and convenient) than the higher-order logic usual in proof assistants, is semi-decidable only because of Gödel's incompleteness theorem. This means a prover for this logic will never terminate on some inputs that are not theorems. There still are interesting provers for FOL, e.g. [E](https://eprover.org https://eprover.org). More restricted fragments that tools can effectively deal with are SAT (purely propositional logic, solvers are very good nowadays) and SMT (SAT + theories such as arithmetic) which is very useful in software verification (e.g. liquid haskell's type system, why3, boogie, F*, etc.). There are people trying to join both domains of research by developing so-called "hammers", that make automatic provers available in proof assistants to make small proof steps entirely automatic.