John McCarthy

Life and career

In the summer of 1955, a young Dartmouth mathematics instructor drafted a funding proposal to the Rockefeller Foundation for a two-month workshop. He needed a name for the subject, one that would distinguish it from cybernetics — a field then dominated by Norbert Wiener's personality — and from automata theory, which sounded too narrow. He wrote "artificial intelligence." The 1956 Dartmouth Summer Research Project on Artificial Intelligence gave the field its name and, more or less, its founding cohort: McCarthy, Marvin Minsky, Claude Shannon, Nathaniel Rochester, and visitors including Allen Newell and Herbert Simon.

John McCarthy was born in Boston in 1927 to politically radical immigrant parents — his father Irish, his mother Lithuanian Jewish, both active Communists during the Depression — and the family moved repeatedly for work and for his health. He was precocious in mathematics, reportedly working through college calculus texts before entering Caltech, where he took his BS in 1948. He heard von Neumann speak on self-replicating automata and was permanently marked by the idea that mental processes might be described mathematically. His PhD came from Princeton in 1951 under Solomon Lefschetz, in a mathematics department that also happened to contain John Nash and, in the town, von Neumann himself.

After Princeton he taught briefly at Stanford and Dartmouth, then moved to MIT in 1956, where with Minsky he founded what became the MIT Artificial Intelligence Laboratory. Those MIT years were extraordinarily productive: LISP, the first proposals for time-sharing, the beginnings of the logic-based approach to commonsense reasoning. In 1962 he returned to Stanford and founded the Stanford Artificial Intelligence Laboratory, which he directed until 1980. SAIL became a distinctive institution — robots, speech, computer music, the first computer-controlled cars in a parking lot, a culture that produced a striking share of the next generation's leaders and, in due course, a good deal of Silicon Valley.

McCarthy was famously contrarian, terse, and indifferent to fashion. He argued in the 1970s that the household robot was decades away and said so publicly when others promised it soon; he also spent forty years insisting that the road to intelligence ran through logic and formalized common sense, long after the field's center of gravity had moved to statistics and learning. He received the Turing Award in 1971, the Kyoto Prize in 1988, and the National Medal of Science in 1990. He remained at Stanford, arguing, until his death in 2011.

Key contributions

**LISP** (1958–1960) is the contribution with the longest shadow. McCarthy's paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" set out a language whose data structures are the same S-expressions used to write its programs, whose semantics rest on the lambda calculus, and whose core can be specified by a short metacircular interpreter — `eval` written in LISP itself. From that design descend a remarkable number of things now taken for granted: garbage collection (McCarthy's invention, forced by the need to reclaim cons cells), first-class functions, recursion as the default control structure, the read–eval–print loop, symbolic computation as a mode of programming, and the idea that a language's specification can be an interpreter rather than a manual. The conditional expression — `if-then-else` as an expression returning a value, rather than a jump — is his, and is now in essentially every language you use.

**Time-sharing.** In 1959 McCarthy circulated a memo at MIT arguing that a single computer should be able to serve many interactive users at once, each with the illusion of a private machine. This was not obvious; batch processing was the norm and interactivity was considered wasteful of expensive hardware. His advocacy fed directly into MIT's CTSS and then Project MAC and Multics, and from there into the whole interactive computing tradition. He also, in a 1961 talk, articulated the idea that computation might one day be sold as a public utility — the cleanest early statement of what we now call cloud computing.

**Formalizing common sense.** This is what McCarthy himself considered his central project. "Programs with Common Sense" (1959) proposed the *Advice Taker*, a hypothetical system that represents what it knows as sentences in a formal logic and derives its actions by deduction — so that you could teach it by telling it new facts rather than reprogramming it. Pursuing that program produced the **situation calculus** (with Patrick Hayes, 1969), a first-order formalism in which fluents are predicates whose truth depends on a situation term, actions map situations to successor situations, and one writes axioms for preconditions and effects. Doing this seriously surfaced the **frame problem**: the difficulty of specifying, without an explosion of axioms, all the things an action does *not* change. McCarthy named it, and it became one of the defining technical and philosophical problems of AI.

His attempted solution, **circumscription** (1980), is a form of nonmonotonic reasoning: rather than enumerate what stays fixed, you minimize the extension of an "abnormality" predicate, licensing the default conclusion that nothing is abnormal unless the premises force it. Circumscription sits alongside Reiter's default logic and McDermott and Doyle's nonmonotonic logic as one of the three canonical formalisms for reasoning that can be *retracted* when new information arrives — a genuinely hard problem for classical logic, where adding premises can only add conclusions.

Alongside these, McCarthy contributed the alpha-beta pruning idea in game-tree search (he is generally credited with the insight and its early formulation, in the context of his chess work), foundational work on the mathematical theory of computation and proving programs correct, and — less famously — an early and clear-eyed treatment of what it would mean to ascribe beliefs and intentions to machines.

In battle

McCarthy's profile is a textbook case of a deep specialist: a mean of 26 across a hundred problems, a median of 18, but five problems above 90 and eight above 70. When his tools apply, they apply completely; when they don't, he has nothing.

His two highest scores are 92, and they mark the two halves of his career. **Sequence the robot's actions** (P190) rewards the man who gave classical planning its vocabulary — situation calculus supplied the representation of world-states as sets of facts, and of actions by preconditions and effects, that STRIPS and its descendants ran on. He did not build Shakey, but Shakey's designers were speaking his language. **A computer shared by fifty** (P245) is time-sharing, which he proposed before it existed and pushed until it did; his `systems` category mean of 65 is the highest of any category he touches.

Close behind, **Color the map, meet the constraints** (P188) at 90 and **Prune the adversary's replies** (P194) at 90 are the two faces of his `search` strength (category mean 52.6 over sixteen problems, easily his broadest area). Constraint satisfaction is symbolic search over formally represented state, and alpha-beta is his own contribution to game-tree pruning. **The imitation game, scored** (P259) at 82 puts him on the question of what counts as machine intelligence — the man who named the field is a natural authority on its criteria. Then **Let the machine find the proof** (P195) at 76, **Prove the program correct** (P048) at 75, and **Three machines, one class** (P155) at 74 round out a coherent picture: automated deduction, program verification, and models of computation are all downstream of the logic-and-recursion program he spent his life on.

The losses are equally coherent, and they are the statistical tide he never joined. He scores 4 on **The paradox in the admissions data** (P214) and 4 on **The therapy the trial reversed** (P215) — Simpson's paradox and confounding — and 3 on **The first randomized trial** (P113), **Three species of iris** (P151), **Calculus for a jagged path** (P216), and **How high must the dike be?** (P217). Fisher's experimental design, discriminant analysis, stochastic calculus, extreme value theory: none of it is in his toolkit at any point in five decades. His category means confirm it — experimental-design 5.5, perception 8.5, information 9.5, classification 10.5, high-dim 11. Note especially the classification number: seventeen problems, mean 10.5. Pattern recognition from data is the single largest blind spot in a career otherwise remarkable for its range.

The pedagogical point is sharper than "he was pre-statistical." McCarthy *chose* logic, publicly and repeatedly, and defended the choice for forty years against a field moving the other way. Play him on planning, constraint satisfaction, game search, verification, and the philosophical foundations of AI and he is close to unbeatable. Play him on anything with a likelihood function in it and he loses to figures with a fraction of his historical stature.