Questions tagged [computer-assisted-proofs]

Proofs that are partially or entirely checked by computer, including those formalised in interactive theorem provers.

Computer-assisted proofs are usually proofs by exhaustion where the number of cases is too large for humans to check by hand. The first major proof of this kind was of the four-colour theorem in 1976, and others have since followed (e.g. all Rubik's Cube positions can be solved in 20 moves).

Once such a proof is encoded in a proof assistant or interactive theorem prover, it becomes formal. Examples of such provers include Coq and HOL Light, the latter of which was used by Hales as part of the Flyspeck project to prove the Kepler conjecture.

55 questions
65
votes
18 answers

Unsolved Problems due to Lack of Computational Power

I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational…
40
votes
12 answers

What are some theorems that currently only have computer-assisted proofs?

What are some theorems that currently only have computer-assisted proofs? For example, there's the four colour theorem. I am very curious about this and would like to generate a list.
Victor
  • 8,096
  • 6
  • 50
  • 109
35
votes
8 answers

Why is there not a system for computer checking mathematical proofs yet (2018)?

As of 2018, mathematical proofs are still being decided by human consensus. i.e. Give the proof to a few capable humans and if none of them can find any errors than they vote that the proof is correct and it can be published. This surely is not a…
23
votes
3 answers

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of computers, there has been much work done related to…
15
votes
1 answer

Conjectures Disproven by the use of Computers?

Question: Is there a list of conjectures (famous or not so famous) that were shown to be false by employing the use of computers? This is just curiosity more than anything. I was actually wondering if more often than not - computers show many…
13
votes
3 answers

Mathematical logic book that uses a proof assistant?

I'm looking for an introductory book on mathematical logic that also discusses an implementation of its logic in a proof assistant. It seems to me this would be a great way to learn mathematical logic, since many concepts would become very clear and…
WillG
  • 6,260
  • 2
  • 19
  • 42
13
votes
2 answers

Examples of the benefits of Homotopy Type Theory for computer aided proofs?

From what I understand, Homotopy Type Theory is proposed as a new foundation of mathematics, and it supposed to be superior for use with computer aided proofs. I am currently trying to understand the theory, but I am also curious as to what…
10
votes
1 answer

Computational Type Theory For Topos Logic

My question is basically, what approaches have been made to make computer proof assistants which can handle the internal logic of a topos ? To explain: while learning topos theory I was struck by the elegance of Mitchell-Bénabou language (the…
9
votes
1 answer

Where can I download the approx 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?

Where can I download computer representations of the approximately 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof? The Wikipedia article (http://en.wikipedia.org/wiki/Four_color_theorem) states "Their proof reduced the…
7
votes
1 answer

Math via Computers

What computer language is best for doing mathematics? That is, which of C or Ruby or whatever would generally be the widest applicable efficient computer language to master for doing mathematics? In response to a question posted below: The idea is a…
user144668
  • 557
  • 4
  • 9
7
votes
1 answer

Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?

I have recently come to discover Metamath. Supposedly the language is one that a computer may proof-check. I then began to look at concepts that I am familiar with, and decided to look up the pigeon hole principle. In their proof, in line 5 I came…
7
votes
1 answer

Which subfields of math are easier or harder to formalize?

This is a follow-up question to Can all math results be formalized and checked by a computer?. Hopefully it's not too broad, but here goes: which subfields of math could be formalized using existing techniques, given infinite time and resources? …
6
votes
2 answers

What is the meaning of proof of a proof?

After reading about Curry-Howard corrsepondence and looking at some proofs written in coq i've thinked about meaning of proof of a proof. We can express proofs as a computer program Proof is correct when program compiles We can test compiled…
featuredpeow
  • 171
  • 2
  • 5
6
votes
1 answer

An Auto-Generated Cartography of Mathematical Theories: Has it been done already?

While looking for a way to visualize the logical structure of mathematical theories a graph-like depiction came to my mind, where propositions are represented by vertices. An edge goes from proposition A to proposition B if A has been used in the…
6
votes
1 answer

Why typeclasses rather than inductive types to define mathematical structures in Lean?

I am not sure whether this is the right forum for this question, but I am not sure where else to ask (There is no Lean forum afaik). In the Lean Prover mathlib library, typical mathematical structures such as groups, are formalized as “typeclasses”.…
1
2 3 4