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. $\lnot A \lor 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^*$.

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.