Proof assistant
(Redirected from Proof verification)
Jump to navigation
Jump to search
In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by humanmachine collaboration. This involves some sort of interactive proof editor, or other interface, with which a human can guide the search for proofs, the details of which are stored in, and some steps provided by, a computer.
Comparison of systems
Name  Latest version  Developer(s)  Implementation language  Features  

Higherorder logic  Dependent types  Small kernel  Proof automation  Proof by reflection  Code generation  
ACL2  7.1  Matt Kaufmann and J Strother Moore  Common Lisp  No  Untyped  No  Yes  Yes^{[1]}  Already executable 
Agda  2.5.1.1  Ulf Norell, Nils Anders Danielsson, and Andreas Abel (Chalmers and Gothenburg)  Haskell  Yes  Yes  Yes  No  Partial  Already executable 
Albatross  0.4  Helmut Brandl  OCaml  Yes  No  Yes  Yes  Unknown  not yet implemented 
Coq  8.8  INRIA  OCaml  Yes  Yes  Yes  Yes  Yes  Yes 
F*  repository  Microsoft Research and INRIA  F*  Yes  Yes  No  Yes  Unknown  Yes 
HOL Light  repository  John Harrison  OCaml  Yes  No  Yes  Yes  No  No 
HOL4  Kananaskis8 (or repo)  Michael Norrish, Konrad Slind, and others  Standard ML  Yes  No  Yes  Yes  No  Yes 
Isabelle  2018  Larry Paulson (Cambridge), Tobias Nipkow (München) and Makarius Wenzel (ParisSud)  Standard ML, Scala  Yes  No  Yes  Yes  Yes  Yes 
Lean  repository  Microsoft Research  C++  Yes  Yes  Yes  Yes  Yes  Unknown 
LEGO (not affiliated with the LEGO company)  1.3.1  Randy Pollack (Edinburgh)  Standard ML  Yes  Yes  Yes  No  No  No 
Mizar  8.1.05  Białystok University  Free Pascal  Partial  Yes  No  No  No  No 
NuPRL  5  Cornell University  Common Lisp  Yes  Yes  Yes  Yes  Unknown  Yes 
PVS  5.0  SRI International  Common Lisp  Yes  Yes  No  Yes  No  Unknown 
Twelf  1.7.1  Frank Pfenning and Carsten Schürmann  Standard ML  Yes  Yes  Unknown  No  No  Unknown 
 ACL2 – a programming language, a firstorder logical theory, and a theorem prover (with both interactive and automatic modes) in the Boyer–Moore tradition.
 Coq – Which allows the expression of mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification.

HOL theorem provers – A family of tools ultimately derived from the LCF theorem prover. In these systems the logical core is a library of their programming language. Theorems represent new elements of the language and can only be introduced via "strategies" which guarantee logical correctness. Strategy composition gives users the ability to produce significant proofs with relatively few interactions with the system. Members of the family include:
 HOL4 – The "primary descendant", still under active development. Support for both Moscow ML and Poly/ML. Has a BSDstyle license.
 HOL Light – A thriving "minimalist fork". OCaml based.
 ProofPower – Went proprietary, then returned to open source. Based on Standard ML.
 Isabelle is an interactive theorem prover, successor of HOL. The main codebase is BSDlicensed, but the Isabelle distribution bundles many addon tools with different licenses.
 Jape – Java based.
 LEGO
 Matita – A light system based on the Calculus of Inductive Constructions.
 MINLOG – A proof assistant based on firstorder minimal logic.
 Mizar – A proof assistant based on firstorder logic, in a natural deduction style, and Tarski–Grothendieck set theory.
 PhoX – A proof assistant based on higherorder logic which is eXtensible.
 Prototype Verification System (PVS) – a proof language and system based on higherorder logic.
 TPS and ETPS – Interactive theorem provers also based on simplytyped lambda calculus, but based on an independent formulation of the logical theory and independent implementation.
 Typelab
 Yarrow
User interface
A popular frontend for proof assistants is the Emacsbased Proof General, developed at the University of Edinburgh. Coq includes CoqIDE, which is based on OCaml/Gtk. Isabelle includes Isabelle/jEdit, which is based on jEdit and the Isabelle/Scala infrastructure for documentoriented proof processing.
See also
 Automated theorem proving
 Computerassisted proof
 QED manifesto
 Satisfiability modulo theories
 Metamath – a language for developing strictly formalized mathematical definitions and proofs accompanied by a proof checker for this language and a growing database of thousands of proved theorems
Notes
 ^ Hunt, Warren; Matt Kaufmann; Robert Bellarmine Krug; J Moore; Eric W. Smith (2005). "Meta Reasoning in ACL2" (PDF). Springer Lecture Notes in Computer Science. 3603: 163–178.
References
 Henk Barendregt and Herman Geuvers (2001). "Proofassistants using Dependent Type Systems". In Handbook of Automated Reasoning.
 Frank Pfenning (2001). "Logical frameworks". In Handbook of Automated Reasoning.
 Frank Pfenning (1996). "The Practice of Logical Frameworks".
 Robert L. Constable (1998). "Types in computer science, philosophy and logic". In Handbook of Proof Theory.
 H. Geuvers. "Proof assistants: History, ideas and future".
 Freek Wiedijk. "The Seventeen Provers of the World"
External links
 "Introduction" in Certified Programming with Dependent Types.
 Introduction to the Coq Proof Assistant (with a general introduction to interactive theorem proving)
 Interactive Theorem Proving for Agda Users
 A list of theorem proving tools
 Catalogues
 Digital Math by Category: Tactic Provers
 Automated Deduction Systems and Groups
 Theorem Proving and Automated Reasoning Systems
 Database of Existing Mechanized Reasoning Systems
 NuPRL: Other Systems
 Specific Logical Frameworks and Implementations
 DMOZ: Science: Math: Logic and Foundations: Computational Logic: Logical Frameworks
This page is based on the copyrighted Wikipedia article "Proof assistant"; it is used under the Creative Commons
AttributionShareAlike 3.0 Unported License (CCBYSA). You may
redistribute it, verbatim or modified, providing that you comply with
the terms of the CCBYSA