This foundational 1956 paper by Allen Newell and Herbert A. Simon introduces the Logic Theory Machine (LT), arguably the first program to demonstrate "artificial intelligence" by performing a task previously thought to require human creativity: proving mathematical theorems. Rather than relying on exhaustive calculation, LT uses "heuristics"—rules of thumb—to navigate the vast search space of symbolic logic.
TL;DR
Newell and Simon present the Logic Theory Machine, a system that mimics human problem-solving to prove theorems in symbolic logic. It marks a historic shift from purely algorithmic computation to heuristic-based "complex information processing," laying the groundwork for the field of Artificial Intelligence.
What Problem Does This Paper Address?
In the mid-1950s, computers were primarily seen as "number crunchers" executing rigid, systematic algorithms. While these algorithms were effective for arithmetic, they failed at complex tasks like theorem proving, where the number of possible logical combinations is astronomically large—a "combinatorial explosion" that makes random or exhaustive search impossible.
The authors sought to bridge the gap between mechanical computation and human thought. They aimed to create a system that didn't just calculate, but discovered proofs by using selective, intelligent strategies to find a path from known axioms to a target theorem.
Methods
The authors introduce two major components: a new programming framework and a set of problem-solving strategies.
- Logic Language (LL): To specify LT, they developed a formal "pseudo-code" designed for complex information processing. Unlike standard machine code, LL handles hierarchical data structures (trees and lists) and supports recursion and iteration.
- Information Processing System (IPS): They define an IPS as a set of memories (working and storage) and processes that act on symbols.
- Heuristic Methods: Instead of a single "master algorithm," LT employs three main heuristic methods to find proofs:
- Substitution: Attempting to match the target theorem to an existing axiom by substituting variables.
- Detachment: Using the rule of Modus Ponens ($A$ and $A \rightarrow B$ implies $B$) to work backward from the goal.
- Chaining: Using the transitivity of implication ($A \rightarrow B$ and $B \rightarrow C$ implies $A \rightarrow C$) to create a bridge between axioms and the goal.
LT uses a "similarity test" to prune its search, only attempting to match theorems that "look like" the target based on features like the number of variables or levels of logic.
Datasets
The system was evaluated using Chapter 2 of Whitehead and Russell’s Principia Mathematica, a seminal work in symbolic logic. This served as the benchmark for LT's "intelligence."
Key Insights and Ideas
- Complexity vs. Computation: The authors argue that "complexity" is not about the amount of processing, but the organization of processes. A complex system is one where the next step is highly contingent on previous outcomes and environmental feedback.
- Heuristics as Search Pruning: The core "aha moment" is that human-like intelligence comes from knowing what not to look at. By using cues to select "similar" theorems, LT reduces the search space from thousands of possibilities to just a handful.
- Working Backward: LT often starts with the theorem it wants to prove and works backward toward the axioms, a strategy the authors observed in human problem-solving.
- List Processing: The paper describes the early implementation of what we now know as "linked lists" and "tree structures" to represent logical expressions, which became a staple of AI programming (eventually leading to the Lisp language).
Key Results
- Success Rate: Using the Substitution Method alone, LT successfully proved 21 out of the 67 theorems in Chapter 2 of Principia Mathematica.
- Advanced Proving: With the addition of Detachment and Chaining, LT proved more complex theorems, such as theorem 2.06, which the authors walk through in detail to show how the machine "discovered" a proof that required multiple intermediate steps.
- Efficiency: The authors demonstrated that while a random search for a 4-step proof might require examining 10,000 chains, LT’s heuristics could reduce that to as few as 16 chains.
Limitations and Future Work
- No Guarantee of Success: Unlike an algorithm, a heuristic method is not guaranteed to find a solution. LT might fail to prove a valid theorem if its search is too narrow or if it hits a "stop rule" (a limit on the amount of "work" or memory used).
- Learning: The version of LT described is primarily a "performance" program. While it "learns" by storing proved theorems to use as future axioms, it does not yet improve its own heuristics over time.
- Hardware Realization: At the time of writing, the system was specified in LL but not yet fully "realized" on a physical computer (though the authors note this work was underway).
- The "Brute Force" Alternative: The authors acknowledge that while LT mimics humans, a sufficiently powerful computer might eventually use "brute force" to outperform these specific heuristics—a tension that still exists in AI today.
Summary updated