search
Let the machine find the proof
It is 1956, and a bold claim is being tested: that a machine can not merely calculate but reason — discover proofs of theorems by searching, as a mathematician does, through the space of possible derivations. Give the machine axioms and inference rules and set it to prove a theorem by searching for a chain of steps from premises to conclusion, where the branching of applicable rules at each step makes brute enumeration hopeless and heuristic guidance essential. This is search over the space of proofs, and it is where symbolic AI stakes its first flag. Get it wrong and either automated reasoning is dismissed as impossible and the symbolic program stillborn, or the search explodes uncontrolled and proves nothing — mechanized theorem proving is the origin of intelligence-as-search.
Who this problem belongs to
The two figures whose methods fit it best, out of 67 in contention.
Newell, with Herbert Simon and programmer Cliff Shaw, built the Logic Theorist in 1955–1956, the program this problem is describing almost exactly: given the axioms and inference rules of Whitehead and Russell's Principia Mathematica, it searched a space of possible derivations and found proofs for 38 of the first 52 theorems in Chapter 2, one of them more elegant than the original. Presented at the 1956 Dartmouth workshop, it is widely considered the first working AI program and the founding demonstration that machine reasoning through search was not merely a philosophical claim but an engineering reality. Newell went on to build increasingly general problem-solving architectures (the General Problem Solver, later Soar) extending exactly this proof-search paradigm to broader domains. No one on this roster fits the problem's specific 1956 framing more precisely.
Simon co-built the Logic Theorist with Newell and Shaw in 1955–1956, the program that first searched a space of logical derivations to prove theorems from Principia Mathematica, and he is the one who reportedly announced to his class in January 1956 that they had 'invented a thinking machine.' His framing of problem solving as heuristic search through a state space — later formalized in Human Problem Solving (1972, with Newell) — is the direct theoretical account of why brute enumeration of proof steps fails and guided search succeeds, precisely the problem's crux. Simon's broader career spanned economics (bounded rationality, a Nobel Prize) and cognitive psychology, using theorem proving as one demonstration domain among several, but this specific problem is his and Newell's founding achievement.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
67 figures are scored on this problem. Draw it in a battle to see where you land.