Theorem Provers: One Size Fits All? CCS: Theory of computation Proof theory CCS: Theory of computation Type theory CCS: Theory of computation Logic and verification
Harrison Oates, Hyeonggeun Yun, Nikhila Gurusinghe · 2025
Read Theorem Provers: One Size Fits All? CCS: Theory of computation Proof theory CCS: Theory of computation Type theory CCS: Theory of computation Logic and verification by Harrison Oates, Hyeonggeun Yun, Nikhila Gurusinghe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15015.txt.
Introduction
Harrison Oates, Hyeonggeun Yun, and Nikhila Gurusinghe test-drive two interactive theorem provers in a 2025 formal methods paper. Theorem provers help people build machine-checked proofs, and today's systems differ widely in design philosophy. Those choices shape how usable each system feels and which problems it suits.
Both provers, Coq and Idris2, are put through the same exercise: proving the correctness of insertion sort, a standard sorting algorithm. The authors then evaluate the experience qualitatively, comparing features, workflow, and the feel of each proof development. Community size and library support get a separate comparison, since a prover is only as useful as the mathematics already formalized for it. The study aims to help newcomers choose a system and to show developers ideas worth borrowing.
Catalog record
| CREATOR | Harrison Oates, Hyeonggeun Yun, Nikhila Gurusinghe |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-15015
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Theorem Provers: One Size Fits All? CCS: Theory of computation Proof theory CCS: Theory of computation Type theory CCS: Theory of computation Logic and verification Harrison Oates, Hyeonggeun Yun, Nikhila Gurusinghe Abstract . Theorem provers are important tools for people working in formal verification. There are a myriad of interactive systems available today, with varying features and approaches motivating their development. These design choices impact their usability, alongside the problem domain in which they are employed. We test-drive two such provers — Coq and Idris2 — by proving the correctness of insertion sort, before providing a qualitative evaluation of their performance. We then compare their community and library support. This work helps users to make an informed choice of system, and highlight approaches in other systems that developers might find useful. 1. Introduction The field of theorem proving systems seems to be at a turning point, with the role of a prover undergoing an evolution from a mere assistant to a necessity. Distinguished Mathematics Professor Kontorovich mentions this in their foreword to the Experimental Mathematics’ Special Issue on Interactive Theorem Provers ( Kontorovich 2022 ) , positing that in the near future highly regarded journals will only accept proofs formalized in theorem proving systems. Going further, Kontorovich states that this is not as radical as it may seem since similar transitions have occurred: there was a point in the 19th century when it became required for calculus research papers to present proofs in Cauchy’s \epsilon / \delta formalism. The necessity of theorem proving systems is further underscored by Nawaz et al. 2019 ( Nawaz et al. 2019 ) , who points to incidents such the 2009 crash of Air France Flight 447 (228 deaths), the 2009 Washington Metro collision (80 severe injuries, 9 deaths); and the infamous Therac 25 incidents, resulting in several peoples’ deaths. These incidents all arose from faulty software and could have been avoided if these systems were validated mathematically; demonstrating why formalisation with theorem provers are a necessity for mission critical systems ( Nawaz et al. 2019 ) . Consequently, the importance of mathematical formalization within the literature justifies a broader understanding of the state of the theorem proving landscape. Comparison studies, especially those focusing on novel theorem proving systems, can adequately provide this within the literature. We make a specific contribution to this domain through comparing the interactive provers Coq and Idris2 for their approach through a user-experience lens. 2. Background 2.1. The provers Coq, first released in 1989, is an interactive theorem prover (ITP) built upon the Calculus of Inductive Constructions ( INRIA-Rocquencourt 2023 ) , a constructive type system, and developed in OCaml. The prover allows users to state theorems and software specifications and then interactively develop formal proofs of these theorems through tactics. Generated proofs are machine-checked by a certification kernel to verify the validity of the developed proof. Some notable uses of Coq include the development of CompCert, a formally-verified optimizing compiler for C99 ( Leroy 2009 ) , as well as a proof of the four colour theorem ( Gonthier 2008 ) . Released in 2020, Idris2 is a relatively new purely functional programming language descended from Idris/Idris1 (initial release 2007) with first class dependent types ( Brady 2021 ) . In contrast to Coq, it is primarily designed as a general-purpose programming language rather than as a dedicated theorem prover. Like Coq, Idris2 uses a constructive logic ( Sitnikovski 2023 ) , but with extensions from quantitative type theory that allow the user to specify when a function can run, not just a function’s intended, proven purpose. The utility of this is immediately apparent, with the developers giving the example of guaranteeing an ATM only dispenses cash at most once per card insertion ( Brady 2021 ) . 2.2. Related work There is no shortage of research comparing theorem provers on the attributes and features associated with them. Many of these are in-depth with expansive investigation such as ( Wiedijk 2003 ) , which offers a fifteen-way comparison of industrial-strength mathematical provers, aiming to demonstrate the variety of approaches available for the problem of formalizing mathematics. These studies tend to focus on the size of the standard library, the strength of their logic, and the level of automation that each system offers. ( Wiedijk 2003 ) was a companion paper to ( Wiedijk 2006 ) , which compiled proofs of the irrationality of \sqrt{2} in a superset of these provers as a means of direct comparison. The latter paper’s focus was on the appearance of proof formalization results, rather than on the formalization experience of users. Other papers, such as ( Nawaz et al. 2019 ) , do not test-drive the provers and instead rely on surveys from developers and online benchmarks to draw their conclusions, although these are fewer in number. However, there is a shortage of research comparing novel theorem provers. This shortage is especially evident for newer systems. Examples include ( Yushkovskiy 2018 ) , ( Zammit 1997 ) , and ( Jakubiec et al. 1997 ) , which all evaluate and compare Coq and Isabelle/HOL –– the regularity of this topic is emblematic of a common trend within the theorem proving comparison literature. Interestingly, this disparity seems to occur independently of the market share of a theorem proving system as for instance Lean — the theorem prover of choice for many studies aiming to formalize mathematical concepts — seems to have very little coverage in terms of studies directly comparing it to other theorem provers. This is because many of the in-depth studies tend to focus on popular and more well-established theorem provers such as Coq or Isabelle/HOL — provers that were released over thirty years ago. As a result, there is a distinct scarcity of literature that compares newer systems such as Idris2 against these well-established theorem provers. Moreover, papers may be rendered obsolete due to their age and subsequent development of the examined systems. As much as this could be justified by how novel these theorem provers are, it is worrying that, in many cases, there is little literature comparing these theorem provers at all. As a result, it is difficult to ascertain the true dimensions of the current theorem proving landscape in terms of what options exist, the power of these options as well as the features that they offer. Zammit mentions this in their comparison of Coq and HOL ( Zammit 1997 ) , stating that many users of theorem provers lack the perspective of knowing more than one such system, justifying this by stating that becoming proficient with a theorem proving system is a time-consuming task. Going further Zammit argues that comparison studies which compare a user’s preferred theorem prover with others concretes their understanding of the system they are familiar with whilst providing them better perspective about others. Hence, these types of studies form an important portion of the literature and can be informative in terms of how one is to go about proving the correctness of a given algorithm. 3. Comparing the provers 3.1. Installing the provers The experience of setting up the provers varied greatly between the systems. Coq provides pre-built binaries for all operating systems, alongside