Automated reasoning
The Cornell Summer meeting of 1957 brought together logicians and computer scientists to discuss the future of machine logic. This gathering is often cited as the birthplace of automated reasoning as a distinct field. Before that event, Martin Davis implemented Presburger's decision procedure in 1954. That program proved that the sum of two even numbers is always even. The Logic Theorist program followed shortly after its development in 1956 by Allen Newell, Cliff Shaw, and Herbert A. Simon. It mimicked human reasoning to prove fifty-two theorems from chapter two of Principia Mathematica. The team successfully proved thirty-eight of them. One proof they found was more elegant than the original version provided by Whitehead and Russell. Their 1958 publication claimed machines could soon handle problems co-extensive with the human mind. Formal proofs require every logical inference to be checked back to fundamental axioms without exception.
Boyer-Moore Theorem Prover began its life in 1971 at Edinburgh, Scotland. John McCarthy and Woody Bledsoe influenced its design significantly. Developers built it using Pure Lisp as both language and working logic. The system relied on a principle of definition for total recursive functions. It used extensive rewriting and symbolic evaluation techniques throughout its operations. An induction heuristic based on the failure of symbolic evaluation drove many of its decisions. HOL Light emerged later as an alternative written in OCaml. Its creators aimed for a simple and clean logical foundation. This tool serves as a proof assistant for classical higher order logic. Rocq developed in France offers another approach to automated proof assistance. It can automatically extract executable programs from specifications into Objective CAML or Haskell source code. Properties, programs, and proofs are all formalized within the same language called the Calculus of Inductive Constructions.
The year 1986 marked the first incompleteness theorem proved by Boyer, Moore. Shankar served as the formalizer for this Gödel result. Quadratic Reciprocity followed in 1990 with Russinoff handling the formalization under Eisenstein's traditional proof. Harrison utilized HOL Light to prove the Fundamental Theorem of Calculus in 1996. Henstock provided the traditional version of that calculus theorem. Two major works appeared in 2000 regarding the Fundamental Theorem of Algebra. Milewski worked with Mizar while Geuvers and colleagues used Rocq, then known as Coq. Gonthier led the effort to formally verify the Four Color Theorem using Rocq in 2004. Avigad and his team applied Isabelle to prove the Prime Number Theorem in 2005. Hales contributed to the Jordan Curve Theorem proof using HOL Light that same year. The Flyspeck project began in 2006 to verify Hales' work on sphere packing. Heule and others solved the Boolean Pythagorean triples problem in 2016 using SAT formalization.
Automated reasoning has been most commonly used to build automated theorem provers. These tools often require human guidance to be effective and thus qualify as proof assistants. Logic Theorist demonstrated how programs could find new approaches to proving a theorem. It produced an efficient proof for one of the theorems in Principia Mathematica requiring fewer steps than Whitehead and Russell's original. Automated reasoning programs solve growing numbers of problems in formal logic and mathematics. They assist in computer science, logic programming, software verification, and hardware design. Circuit design benefits from these logical methods as well. The TPTP library contains a collection of such problems updated regularly by Sutcliffe and Suttner. A competition among automated theorem provers occurs regularly at the CADE conference. Problems for this competition are selected directly from the TPTP library. Microsoft started using verification technology in many internal projects during 2005. The company planned to include a logical specification and checking language in its 2012 version of Visual C.
John Pollock created the OSCAR system as an example of automated argumentation. This tool is more specific than being just an automated theorem prover. It applies constraints of minimality and consistency on top of standard automated deduction. Reasoning under uncertainty forms another important part of the field. Bayesian inference serves as a key technique within that uncertainty framework. Fuzzy logic provides additional tools for handling imprecise information. Systems can reason with maximal entropy when dealing with incomplete data. Ad hoc techniques exist alongside classical logics and calculi for less formal situations. These methods allow machines to handle scenarios where strict binary logic fails. Non-monotonic reasoning enables systems to revise conclusions when new information arrives. Such flexibility mirrors human thought processes better than rigid proof systems alone.
AI researchers designed reasoning language models in the 2020s to enhance large language model capabilities. These models spend additional time on problems before generating answers. Neuro-symbolic architectures now reason in formal logic to prevent hallucinations. This approach combines neural networks with symbolic reasoning rules. The goal is to reduce errors while solving complex problems. Automated reasoning helps produce computer programs that allow computers to reason completely or nearly completely automatically. Connections remain strong between theoretical computer science and philosophy despite the artificial intelligence label. Extensive work continues in reasoning by analogy using induction and abduction. The field has revived after an AI winter period during the eighties and early nineties. Current research focuses on making these systems more robust and reliable for real-world tasks.
Common questions
When was automated reasoning established as a distinct field?
Automated reasoning was established as a distinct field at the Cornell Summer meeting of 1957. This gathering brought together logicians and computer scientists to discuss machine logic.
Who developed the Logic Theorist program in 1956?
Allen Newell, Cliff Shaw, and Herbert A. Simon developed the Logic Theorist program in 1956. It successfully proved thirty-eight out of fifty-two theorems from chapter two of Principia Mathematica.
What year did Boyer and Moore prove the first incompleteness theorem using automated reasoning?
Boyer and Moore proved the first incompleteness theorem in 1986 with Shankar serving as the formalizer for this Gödel result. Quadratic Reciprocity followed in 1990 with Russinoff handling the formalization under Eisenstein's traditional proof.
Which software tools are used for automated proof assistance today?
HOL Light serves as a proof assistant for classical higher order logic while Rocq offers another approach written in OCaml. These systems allow users to extract executable programs from specifications into Objective CAML or Haskell source code.
How does Microsoft use verification technology in its projects?
Microsoft started using verification technology in many internal projects during 2005. The company planned to include a logical specification and checking language in its 2012 version of Visual C.
All sources
20 references cited across the entry
- 2webDeepseek-R1 triggers boom in reasoning-enabled language modelsJonathan Kemper — 2025-05-11
- 3journalNeurosymbolic AI is the answer to large language models’ inability to stop hallucinatingArtur Garcez — 30 May 2025
- 4journalHow good old-fashioned AI could spark the field's next revolutionNicola Jones — 2025
- 5newsMeet Neurosymbolic AI, Amazon's Method for Enhancing Neural NetworksSteven Rosenbush — 2025-08-12
- 8bookAutomation of Reasoning (1) — Classical Papers on Computational Logic 1957–1966Martin Davis — Springer — 1983
- 12citationMetamathematics, Machines, and Gödel's ProofN. Shankar — Cambridge University Press — 1994
- 13citationA Mechanical Proof of Quadratic ReciprocityDavid M. Russinoff — 1992
- 14citationInteractive Theorem ProvingG. Gonthier et al. — 2013
- 15bookTheory and Applications of Satisfiability Testing – SAT 2016Marijn J. H. Heule et al. — 2016
- 20webAutomated Reasoning2025