Editing Automated theorem proving (section)

==First-order theorem proving==
In the late 1960s agencies funding research in automated deduction began to emphasize the need for practical applications.{{citation needed|date=December 2023}} One of the first fruitful areas was that of [[program verification]] whereby first-order theorem provers were applied to the problem of verifying the correctness of computer programs in languages such as [[Pascal (programming language)|Pascal]], [[Ada (programming language)|Ada]], etc. Notable among early program verification systems was the Stanford Pascal Verifier developed by [[David Luckham]] at [[Stanford University]].<ref>{{cite report |url=https://apps.dtic.mil/sti/citations/ADA027455 |title=Automatic Program Verification V: Verification-Oriented Proof Rules for Arrays, Records, and Pointers |author=Luckham |first1=David C. |last2=Suzuki |first2=Norihisa |date=Mar 1976 |archive-url=https://web.archive.org/web/20210812180903/https://apps.dtic.mil/sti/citations/ADA027455 |archive-date=August 12, 2021 |url-status=live |institution=[[Defense Technical Information Center]] |type=Technical Report AD-A027 455}}</ref><ref>{{cite journal | doi=10.1145/357073.357078 | first1=David C. |last1=Luckham |first2=Norihisa |last2=Suzuki | title=Verification of Array, Record, and Pointer Operations in Pascal | journal=[[ACM Transactions on Programming Languages and Systems]] | volume=1 | number=2 | pages=226–244 | date=Oct 1979 | s2cid=10088183 | doi-access=free }}</ref><ref>{{cite tech report | url=https://exhibits.stanford.edu/stanford-pubs/catalog/nh154bt5645 |first1=D. |last1=Luckham |first2=S. |last2=German |first3=F. |last3=von Henke |first4=R. |last4=Karp |first5=P. |last5=Milne |first6=D. |last6=Oppen |first7=W. |last7=Polak |first8=W. |last8=Scherlis | title=Stanford Pascal verifier user manual | institution=Stanford University | id=CS-TR-79-731 | year=1979 }}</ref> This was based on the Stanford Resolution Prover also developed at Stanford using [[John Alan Robinson]]'s [[Resolution (logic)|resolution]] principle. This was the first automated deduction system to demonstrate an ability to solve mathematical problems that were announced in the ''[[Notices of the American Mathematical Society]]'' before solutions were formally published.{{citation needed|date=September 2020}}

[[First-order logic|First-order]] theorem proving is one of the most mature subfields of automated theorem proving. The logic is expressive enough to allow the specification of arbitrary problems, often in a reasonably natural and intuitive way. On the other hand, it is still semi-decidable, and a number of sound and complete calculi have been developed, enabling ''fully'' automated systems.<ref>{{Cite book |last=Loveland |first=D. W. |title=Proceedings of the ACM SIGART international symposium on Methodologies for intelligent systems |date=1986 |publisher=ACM Press |isbn=978-0-89791-206-8 |location=Knoxville, Tennessee, United States |page=224 |language=en |chapter=Automated theorem proving: Mapping logic into AI |doi=10.1145/12808.12833 |doi-access=free |s2cid=14361631}}</ref> More expressive logics, such as [[higher-order logic]]s, allow the convenient expression of a wider range of problems than first-order logic, but theorem proving for these logics is less well developed.<ref>Kerber, Manfred. "[https://kluedo.ub.uni-kl.de/files/364/seki_4.pdf How to prove higher order theorems in first order logic]." (1999).</ref><ref>Benzmüller, Christoph, et al. "[https://page.mi.fu-berlin.de/cbenzmueller/papers/C26.pdf LEO-II-a cooperative automatic theorem prover for classical higher-order logic (system description)]." International Joint Conference on Automated Reasoning. Berlin, Germany and Heidelberg: Springer, 2008.</ref>

===Relationship with SMT===

There is substantial overlap between first-order automated theorem provers and [[satisfiability modulo theories|SMT solver]]s. Generally, automated theorem provers focus on supporting full first-order logic with quantifiers, whereas SMT solvers focus more on supporting various theories (interpreted predicate symbols). ATPs excel at problems with lots of quantifiers, whereas SMT solvers do well on large problems without quantifiers.<ref>{{Cite journal |last1=Blanchette |first1=Jasmin Christian |last2=Böhme |first2=Sascha |last3=Paulson |first3=Lawrence C. |date=2013-06-01 |title=Extending Sledgehammer with SMT Solvers |url=https://doi.org/10.1007/s10817-013-9278-5 |journal=Journal of Automated Reasoning |language=en |volume=51 |issue=1 |pages=109–128 |doi=10.1007/s10817-013-9278-5 |s2cid=5389933 |issn=1573-0670|quote=ATPs and SMT solvers have complementary strengths. The former handle quantifiers more elegantly, whereas the latter excel on large, mostly ground problems.}}</ref> The line is blurry enough that some ATPs participate in SMT-COMP, while some SMT solvers participate in [[CADE ATP System Competition|CASC]].<ref>{{Cite journal |last1=Weber |first1=Tjark |last2=Conchon |first2=Sylvain |last3=Déharbe |first3=David |last4=Heizmann |first4=Matthias |last5=Niemetz |first5=Aina |last6=Reger |first6=Giles |date=2019-01-01 |title=The SMT Competition 2015–2018 |journal=Journal on Satisfiability, Boolean Modeling and Computation |language=en |volume=11 |issue=1 |pages=221–259 |doi=10.3233/SAT190123|quote=In recent years, we have seen a blurring of lines between SMT-COMP and CASC with SMT solvers competing in CASC and ATPs competing in SMT-COMP.|doi-access=free }}</ref>