← Back to home

Automated Reasoning

Right. So, you want me to… illuminate this rather dry subject. Fascinating. Like asking a raven to polish a pebble. Fine. Let’s see if we can inject some, shall we say, gravitas into this dry recitation of facts. Don’t expect sunshine and rainbows. This is about logic, after all. And logic, much like a well-placed shadow, is rarely comforting.

Subfield of Computer Science and Logic

This section is a placeholder, really. A monument to what has been, and a grim reminder of what’s still being chipped away at. It’s about the pursuit of understanding reasoning, not the messy, intuitive kind we stumble through, but the clean, rigorous, absolute kind. In the labyrinthine world of computer science, particularly within the shadowed alleys of knowledge representation and reasoning and the stark geometry of metalogic, lies the domain of automated reasoning. It’s the cold, hard attempt to distill thought into algorithms, to make machines think, or at least mimic the process with a chilling precision. The ultimate goal? To forge computer programs capable of reasoning with a completeness that, frankly, most humans only dream of. It’s a sub-field of artificial intelligence, yes, but its roots run deeper, entwined with the stark landscapes of theoretical computer science and the existential questions of philosophy.

The most polished facets of automated reasoning are undoubtedly automated theorem proving and its slightly more approachable cousin, interactive theorem proving. Then there's automated proof checking, which is less about discovery and more about rigorous validation – ensuring that what’s presented as fact, under a given set of assumptions, is indeed irrefutable. A comforting thought, if you’re into that sort of thing. [ citation needed ] But the landscape isn’t just sharp angles and formal proofs. There’s been considerable effort poured into reasoning by analogy, a more slippery concept, and by employing induction and abduction. [1] These are the attempts to bridge the gap between the purely deductive and the more speculative, like trying to find a pattern in the static.

And then there are the darker corners: reasoning under uncertainty and the inherently unsettling nature of non-monotonic reasoning. The former grapples with incomplete information, the latter with conclusions that can be retracted as new evidence emerges – a perfect metaphor for existence, wouldn't you agree? Within the realm of uncertainty, argumentation takes center stage, layering constraints of minimality and consistency onto the already complex scaffolding of automated deduction. John Pollock’s OSCAR system, for instance, is a testament to this, a system more nuanced than a mere theorem prover. It’s an automated argument system, attempting to navigate the grey areas.

The tools and techniques employed are as varied as they are precise. From the unyielding structure of classical logics and their calculi, to the fuzzy ambiguities of fuzzy logic, the probabilistic certainties of Bayesian inference, and the stark elegance of the principle of maximum entropy. And, of course, a host of less formal, more ad hoc methods, born of necessity and perhaps a touch of desperation.

Even now, in the 2020s, the quest continues. To imbue large language models with a semblance of true problem-solving prowess, researchers are forging reasoning language models. These are designed not for instant gratification, but to allow for a contemplative pause, a deliberate processing time before the answer is delivered. It’s a subtle acknowledgment that true understanding, even for a machine, requires more than just speed. [2]

Early Years

The genesis of automated reasoning is inextricably linked to the evolution of formal logic, a crucial precursor that paved the way for the very concept of artificial intelligence. A formal proof is not for the faint of heart. It’s a rigorous chain of deduction where every single logical inference is traced back to the foundational axioms of mathematics. No steps are skipped, no intuitive leaps are permitted. The translation from raw thought to logical form is absolute, leaving no room for the comfortable ambiguity of human intuition. This meticulousness, while less accessible, drastically reduces the margin for error. [3]

Some point to the Cornell Summer meeting of 1957 as the crucible where automated reasoning, or automated deduction as it was then known, was truly forged. It was a convergence of minds, logicians and computer scientists alike, all wrestling with the same profound questions. [4] Others argue for an earlier origin, perhaps with Newell, Shaw, and Simon’s 1955 Logic Theorist program, or even Martin Davis’s 1954 implementation of Presburger's decision procedure, a rather elegant proof that the sum of two even numbers is, predictably, even. [5]

Despite its significance and the fervent research it inspired, automated reasoning, like many ambitious fields, experienced its own period of disillusionment – an "AI winter" that cast a long shadow over the eighties and early nineties. Yet, the field, like a persistent weed, found its way back to the light. Microsoft, for instance, began integrating verification technology into their internal projects around 2005, with plans to embed logical specification and checking languages into their Visual C compiler by 2012. [4] It’s a testament to the enduring power of rigorous logic, even when faced with the fickle winds of technological trends.

Significant Contributions

The monumental work of Alfred North Whitehead and Bertrand Russell, Principia Mathematica, stands as a cornerstone in the edifice of formal logic. Its ambitious aim was to construct the entirety of mathematical expressions from the bedrock of symbolic logic. Published in three volumes between 1910 and 1913, it was the successor to Russell’s 1903 treatise, The Principles of Mathematics, where he first unveiled his infamous paradox and articulated the thesis that mathematics and logic were, in essence, one and the same.

Then there was Logic Theorist (LT), a groundbreaking program conceived in 1956 by Allen Newell, Cliff Shaw, and Herbert A. Simon. It was designed to “mimic human reasoning” in the arduous task of proving theorems. Presented with fifty-two theorems from chapter two of Principia Mathematica, LT managed to prove thirty-eight of them. More than just a proof generator, it devised a proof for one theorem that was demonstrably more elegant than the original presented by Whitehead and Russell. Their report in 1958, "The Next Advance in Operation Research," painted a rather audacious picture:

"There are now in the world machines that think, that learn and that create. Moreover, their ability to do these things is going to increase rapidly until (in a visible future) the range of problems they can handle will be co-extensive with the range to which the human mind has been applied." [8]

A bold prediction, indeed.

Examples of Formal Proofs

The following table illustrates the progression of formal proofs, showcasing the theorem, the proof system employed, the formalizer, and the traditional proof it sought to replicate or surpass. It's a stark reminder of the meticulous, often painstaking, effort involved in rendering abstract mathematical truths into undeniable, machine-verifiable sequences.

Year Theorem Proof System Formalizer Traditional Proof
1986 First Incompleteness Boyer-Moore Shankar [9] Gödel
1990 Quadratic Reciprocity Boyer-Moore Russinoff [10] Eisenstein
1996 Fundamental Theorem of Calculus HOL Light Harrison Henstock
2000 Fundamental Theorem of Algebra Mizar Milewski Brynski
2000 Fundamental Theorem of Algebra Coq Geuvers et al. Kneser
2004 Four Color Theorem Coq Gonthier Robertson et al.
2004 Prime Number Theorem Isabelle Avigad et al. Selberg-Erdős
2005 Jordan Curve Theorem HOL Light Hales Thomassen
2005 Brouwer Fixed Point Theorem HOL Light Harrison Kuhn
2006 Kepler Conjecture Isabelle Bauer-Nipkow Hales
2007 Cauchy Residue Theorem HOL Light Harrison Classical
2008 Prime Number Theorem HOL Light Harrison Analytic proof
2012 Feit-Thompson Theorem Coq Gonthier et al. [11] Bender, Glauberman and Peterfalvi
2016 Boolean Pythagorean Triples Problem SAT Heule et al. [12] None

Proof Systems

  • Boyer-Moore Theorem Prover (NQTHM): This system, influenced by the minds of John McCarthy and Woody Bledsoe, began its life in Edinburgh in 1971. It was a fully automatic theorem prover, ingeniously constructed using Pure Lisp. Its defining characteristics included:

    • The use of Lisp not just as a programming language, but as the very logic in which proofs were constructed.
    • A fundamental reliance on a principle of definition for total recursive functions.
    • The extensive application of rewriting and "symbolic evaluation" to simplify and transform expressions.
    • A heuristic for induction, triggered by the failure of symbolic evaluation – a clever way to prompt the system when it hit a wall. [13] [14]

  • HOL Light: Written in the elegant OCaml, HOL Light is a testament to the beauty of simplicity. Its design prioritizes a clean logical foundation and an uncluttered implementation. It functions as a proof assistant for classical higher-order logic, a sophisticated tool for those who appreciate precision. [15]

  • Coq: Developed in France, Coq is another formidable automated proof assistant. Its capabilities extend to the automatic extraction of executable programs from specifications, yielding source code in either Objective CAML or Haskell. Within Coq, properties, programs, and proofs are all formalized within the same expressive language: the Calculus of Inductive Constructions (CIC). [16]

Applications

Automated reasoning has found its most common application in the construction of automated theorem provers. However, these provers often require a guiding hand, a human touch to steer them towards effectiveness, thus qualifying them more broadly as proof assistants. In some instances, these systems have unearthed novel approaches to proving theorems. The aforementioned Logic Theorist serves as a prime example, discovering a proof for a theorem in Principia Mathematica that was more concise than the one originally presented by Whitehead and Russell. The reach of automated reasoning programs is steadily expanding, tackling increasingly complex problems across formal logic, mathematics, and computer science. They are vital in areas like logic programming, software and hardware verification, and circuit design, among many others. The TPTP ([Automated_theorem_proving]) library, curated by Sutcliffe and Suttner in 1998, serves as a repository of such problems, regularly updated. Furthermore, a competition for automated theorem provers is held periodically at the CADE conference, with problems drawn from the TPTP library, fostering innovation and a bit of competitive spirit amongst these logical engines. [17]

See Also

Conferences and Workshops

Journals

Communities