Weak methods: the Logic Theorist, GPS & means-ends analysis

What "weak" means

A weak method is a problem solver that is domain-general — it works across many domains precisely because it does not rely on domain-specific knowledge. "Weak" is about generality, not capability. The trade-off is the recurring theme of this course: without strong domain knowledge to guide it, the search space explodes combinatorially, so weak methods live or die by their search strategies.

The weak-method triple

Every weak-method automated-reasoning system has three essential components:

1. A uniform representation medium — a single formal language (predicate calculus, clause form, Horn-clause calculus) in which all knowledge is expressed consistently.
2. Sound (and ideally complete) inference rules — formal rules that preserve truth; resolution is the archetype.
3. Search strategies (heuristics) — methods for controlling which inference rule to apply, and in what order, to fight the combinatorial explosion.

Strategy design is famously called "an art": no general science tells you the best strategy for a given problem, and even an excellent strategy cannot guarantee a useful solution within reasonable time and memory. This is the formal analog of the "art" of knowledge engineering in expert systems.

The Logic Theorist (1956) — the first AI program

Newell, Shaw, and Simon's Logic Theorist proved theorems in propositional logic (from Russell & Whitehead's Principia). It used three inference rules: substitution (replace a variable in a known theorem with an expression), replacement (swap a connective for an equivalent form, e.g. $\neg A\vee B$ for $A\to B$), and detachment (modus ponens). Its decisive idea was matching: a difference measure picked the axiom most similar to the goal, confirmed the matching parts, and identified the specific difference to address — pruning the space of applicable rules by focusing on the most relevant moves. This is the earliest example of heuristic search guidance in AI, the direct ancestor of the heuristic $h(n)$ in $A^{\ast }$.

GPS and means-ends analysis

GPS (General Problem Solver, Newell & Simon, 1963) generalized that idea into means-ends analysis:

1. Compare the current state to the goal.
2. Identify the most significant difference between them.
3. Select an operator that reduces that difference (looked up in a difference table).
4. Recurse: if the operator's preconditions are not met, set up reducing that sub-difference as a new subgoal.

Worked example — the difference table is the swappable part. The difference table indexes operators by the kind of difference each can reduce (e.g. "add a term," "change a connective," "change sign"), with a priority ordering so the most significant difference is attacked first. The means-ends algorithm is domain-general; the table is the domain-specific component you swap when moving from propositional logic to the Towers of Hanoi to chess. That modularity — general procedure, swappable knowledge — is what made GPS "general," and it directly influenced STRIPS (which replaces the difference table with precondition/add/delete lists) and modern production systems (where rules are operators indexed by triggering conditions). GPS was also the first AI program studied as a model of human cognition, founding information-processing psychology.