7
$\begingroup$

I am a high school senior going into college and I am applying to a scholarship in which I must write an essay about a potential future technology that would dramatically impact humans. I immediately thought of proof assistants, which already exist, but I'm sure there are some limitations that can be overcome. I don't really know much about proof assistants, so I would like to learn more. I feel as though they might help to prove significant theorems that we currently have no answer to (if not already) that can benefit humanity massively.

If you could respond or link me to a place where I could learn more about the current state of proof assistants, I would greatly appreciate it. Here are some important questions I have:

  1. What types of theorems can proof assistants solve, and what types can they not at the present moment?
  2. How can they be improved?
  3. What avoidable and unavoidable limitations are there?
  4. Is there anything else I should know about the current and potential future states of proof assistants?
$\endgroup$
2

1 Answer 1

13
$\begingroup$

These are broad questions and I doubt you will get a complete answer in a single stack exchange answer. But since you seem ernest and interested, let me at least try to help clarify some of your questions.

What types of theorems can proof assistants solve, and what types can they not at the present moment?

First, to be clear, the primary purpose of proof assistants isn't to solve new theorems in mathematics automatically. It is to help a human write proofs in an air-tight form. Think of them as a programing language but instead of writing code, you write a proof---and instead of compiling and running the code, the computer checks that the proof is correct.

The three primary use cases of proof assistants are:

  1. To prove the correctness of computer code and hardware. Unlike mathematical proofs, these proofs are very tedious and a small missing case could mean the difference between correct code and a costly bug. Proof assistants help to do this tedious work and not miss edge cases.
  2. To build a library of formal mathematics. By formalizing all of mathematics we can begin to make mathematics more accessible to computers and unify all of mathematics into a few curated digital libraries of mathematics.
  3. To explore new types of logical systems. New logics can be unintuitive and formal systems can help work with them. Conversely, new foundational systems may be better suited for formalizing mathematics on a computer.

A related technology called automated theorem provers are used to prove theorems automatically. SAT solvers, SMT solvers, and resolution theorem provers are some examples. They are often used for industrial applications, but they also have been used to solve certain combinatorial theorems.

Having said all this, there is a continuum between proof assistants and automated theorem provers. More proof assistants have some levels of automation (some using full powered automated theorem provers) which fill in "obvious proof steps". Further a lot of current work in AI theorem proving uses data from proof assistant libraries to train AI models.

Now, if I misunderstood your question and you meant what types of theorems can a proof assistant be used for formalize, here is the answer: In principle, all correct theorems should be formalizable since they follow from the axioms of mathematics. In practice, some types of mathematics are easier than others. Obviously, theorems like Fermat's Last Theorem which both depend on a lot of other kinds of mathematics and are large proofs in themselves, would be a lot of work to formalize. It is better to build a library of mathematics slowly adding in more and more until you have the theorems and tools you need to prove modern theorems.

Also, some subjects like calculus and statistics are import so we teach them to college freshman, but their foundations are actually quite complicated making them difficult to formalize.

How can they be improved?

Usability is a big concern. Proof assistants are still hard to work with. Formalizing is slow and it is a specialized skill. Adding the state of art in program language design and interactive development environment tools would help.

Mathematics in a proof assistant is also very different looking than informal mathematics. Bridging this gap would go a long way to speeding up formal proofs.

Better automation might help. Then the user could have the computer fill in the obvious and not-so-obvious steps. A dream would even have a computer system which could auto-formalize mathematics from say an informal LaTeX proof to a formal proof. This is incredible challenging, but an exciting research goal.

Proof repair is an interesting topic. Proofs break if you change the theorem you are proving. This is especially common when proving the correctness of a piece of computer code which is subject to change. But in many cases, it should be straight forward to repair the proof, and the computer in principle should be able to do it for you.

There are many proof assistants, but they are incompatible with each other. A proof in one proof assistant isn't usable by any other proof assistants. Better interchangeability would go a long way.

There is also the problem that formalization is not well rewarded in academics or industry.

What avoidable and unavoidable limitations are there?

I think I mentioned many avoidable limitations.

As far as unavoidable ones, baring human-level artificial intelligence, it is likely going to continue to be a somewhat tedious human process which gets progressively easier with better tools.

Is there anything else I should know about the current and potential future states of proof assistants?

Probably. But at the same time, just get started playing with proof assistants if they interest you. They are video-game level addictive! I recommend the natural number game as a fun starting point. After doing that, pick a proof assistant that interests you, get to know the community, and start formalizing stuff!

$\endgroup$
1
  • $\begingroup$ Oh okay, I see. I guess I misunderstood what proof assistants were about. Perhaps I was thinking about the automated theorem provers, which I will look into. I have recently watched a few videos about how proof assistants work, and they seem very interesting. Thank you so much for your response; it was very informative. I also appreciate the game you linked, I have been playing around with it a bit :) $\endgroup$
    – gmod
    Commented May 31, 2022 at 5:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.