Stephen Kleene

Abstract

Stephen Cole Kleene (1909–1994), a logician at the University of Wisconsin and a student of Alonzo Church, was one of the founders of the theory of computable functions. In the 1930s he worked out, with Church and others, the equivalence of the different definitions of “effectively calculable,” gave the theory of recursive functions its standard form, and later named the claim that they capture computation “Church’s thesis.” In the summer of 1951, at the RAND Corporation, he asked which patterns of input a network of idealized neurons could recognize, and answered with regular events, a notation built from union, concatenation and an iteration operator now called the Kleene star, together with the theorem that finite automata recognize exactly these patterns. Seventeen years later Ken Thompson turned Kleene’s notation into a text-search command, and regular expressions became one of the most widely used pieces of theoretical computer science.

Stephen Cole Kleene in 1978. Image: Konrad Jacobs, Erlangen (copyright MFO), CC BY-SA 2.0 DE, via Wikimedia Commons.

Hartford and Maine

Stephen Cole Kleene was born on 5 January 1909 in Hartford, Connecticut. His father, Gustav Adolph Kleene, was a professor of economics at Trinity College in Hartford; his mother, Alice Lena Cole, was a poet and playwright. His “real home,” Saunders Mac Lane wrote in his memoir for the National Academy of Sciences, was the family farm in Union, Maine. Kleene kept it all his life and used it as a base for climbing in the mountains of Maine and New Hampshire. Mac Lane opened the memoir with the line: “Steve Kleene, a Yankee from Maine, became a pioneer mathematical logician.”

He graduated summa cum laude from Amherst College in 1930 and went to Princeton for graduate study in mathematics. His surname gave trouble from the start: he pronounced it “KLAY-nee,” a pronunciation that his son Ken later said “is incorrect in all known languages” and that his father had invented himself.

Church’s Students

At Princeton, Kleene and his fellow student J. Barkley Rosser worked under Alonzo Church, who was developing the lambda calculus as a foundation for logic (see Alonzo Church and Lambda Calculus). Kleene and Rosser showed that Church’s original system was inconsistent, a result now called the Kleene-Rosser paradox. The part of the system that dealt only with functions survived as the pure lambda calculus.

Church gave Kleene the problem of developing the theory of positive integers within his system. The first obstacle, Kleene recalled in a 1984 interview with William Aspray, was the predecessor function, the function that subtracts one. He proposed changing the representation of the integers to make it easy; Church objected that he had set up the integers “in such a way that the definition by induction works.” Kleene found a way within Church’s representation and went on to show that a long list of arithmetic functions were “lambda-definable.” He submitted his thesis, “A Theory of Positive Integers in Formal Logic,” in 1933 and received his doctorate in 1934, then stayed on at Princeton as a research assistant. “Mostly I worked on my own,” he said of his time with Church.

The more functions Kleene defined, the more plausible it became that every effectively calculable function was lambda-definable, and Church came to propose exactly that. In 1934 Kurt Gödel lectured at Princeton and introduced a different definition, the general recursive functions, built up from simple functions by composition, recursion and minimization. Kleene took up Gödel’s definition and proved the normal form theorem: every general recursive function can be computed by a single search for the least number satisfying a fixed, simple condition, followed by a fixed simple function. Lambda-definability, general recursiveness and the machine definition that Turing published in 1936 were soon proved to describe the same functions (see Automata Theory and Computability). Turing’s definition, Kleene said, gave immediate support to Church’s thesis because it was “intrinsically plausible,” whereas with the other two “a person became convinced only after he investigated and found, much by surprise, how much could be done with the definition.” He still found recursive functions easier to work with than “complicated Turing-machine tables.”

Wisconsin and the War

In 1935, when he had expected to spend a year at the Institute for Advanced Study, a telegram offered him an instructorship at the University of Wisconsin in Madison, and he accepted. He stayed there, apart from interruptions, for the rest of his career. In 1943 he published the “Thesis I” that every effectively calculable function is general recursive, framing it explicitly as a thesis rather than a theorem, and in the 1940s he introduced the arithmetical hierarchy, which classifies sets of numbers by the number of alternating quantifiers needed to define them and so measures how far beyond the computable a problem lies.

He spent 1941–42 at Amherst. During the Second World War he served in the US Naval Reserve, first teaching navigation and then as a project director at the Naval Research Laboratory, leaving as a lieutenant commander, and in 1942 he married Nancy Elliott; they had four children. In 1946 he returned to Wisconsin as an associate professor and became a full professor in 1948. In 1945 he had published his theory of realizability, which interprets the proofs of intuitionistic mathematics as computations: a statement is “realized” by a number that encodes an algorithm witnessing it. In 1950 he spent time in Amsterdam as a Guggenheim Fellow, consulting the Dutch intuitionists of L. E. J. Brouwer’s school.

Nerve Nets

In 1943 the neurophysiologist Warren McCulloch and the logician Walter Pitts had described idealized neurons that fire when the weighted sum of their inputs exceeds a threshold, and showed that networks of them could compute logical functions. John von Neumann had written notes on automata built from such elements. In the summer of 1951 Kleene spent time at the RAND Corporation, and in August he worked on a question the McCulloch-Pitts paper left open: which patterns of input over time can such a network recognize?

His answer, issued as RAND Research Memorandum RM-704, “Representation of Events in Nerve Nets and Finite Automata,” dated 15 December 1951, introduced what he called regular events. They are built from single inputs by three operations: union (either this pattern or that), concatenation (this followed by that), and iteration (any number of repetitions of a pattern, including none), written with a star, E*. Kleene proved that a McCulloch-Pitts network, and more generally any finite automaton, a machine with a fixed finite number of internal states, can recognize exactly the regular events. The theorem in both directions, from expressions to machines and from machines to expressions, is now called Kleene’s theorem, and the star is called the Kleene star.

The memorandum was published in 1956 in Automata Studies, the volume edited by Claude Shannon and John McCarthy, and it became one of the founding texts of automata theory. Michael Rabin and Dana Scott’s work on nondeterministic finite automata (1959) and Noam Chomsky’s hierarchy of grammars, in which regular languages form the lowest level, built on it (see The Chomsky Hierarchy).

From Theorem to grep

In June 1968 Ken Thompson of Bell Labs published “Regular Expression Search Algorithm” in Communications of the ACM. It described how to search text for a pattern written in Kleene’s notation by translating the expression into a nondeterministic automaton and simulating it, compiled on the fly into IBM 7094 machine code. Thompson built the method into the QED text editor on the CTSS time-sharing system, then into the Unix editor ed, and from ed came the command grep, named after ed’s command g/re/p, “globally search for a regular expression and print” (see Ken Thompson and Unix).

From there regular expressions spread into every Unix tool, into Perl, and into the standard libraries of nearly every programming language, where they validate input, tokenize source code and search logs. The practical versions added features such as back-references that go beyond Kleene’s regular events and cannot be recognized by finite automata, but the core of union, concatenation and star is his. Kleene’s 1951 operations also became the basis of Kleene algebra, used in reasoning about programs.

Introduction to Metamathematics

Kleene’s textbook Introduction to Metamathematics (1952) became the standard reference of its field for a generation and was translated into Russian, Chinese, Romanian and Spanish. It gave a careful account of Gödel’s incompleteness theorems and of recursive function theory, and in it Kleene named “Church’s thesis” and “Turing’s thesis,” arguing that the two were equivalent, and used the combined name Church-Turing thesis. The logician Robert Soare later called Kleene’s formulation of the computable functions through six schemata “one of the most succinct and useful.”

In 1954 he and Emil Post published a joint paper on degrees of unsolvability that shaped later work on Post’s problem (see Emil Post), and in 1955 he introduced the hyperarithmetical hierarchy, which extends the arithmetical one into the transfinite. With Richard Vesley he wrote a book on the foundations of intuitionistic mathematics. He was president of the Association for Symbolic Logic from 1956 to 1958 and supervised at least thirteen doctoral students at Wisconsin, among them John Addison, Clifford Spector, Yiannis Moschovakis and the computer scientist Robert Constable. He brought Rosser to Madison to direct the Army’s Mathematics Research Center.

Later Years

Kleene held a named professorship from 1964 until his retirement in 1979, chaired the mathematics department twice and was dean of the College of Letters and Science from 1969 to 1974. He was elected to the National Academy of Sciences in 1969. His wife Nancy died in 1970; in 1988 he married Jeanne Steinmetz. He received the American Mathematical Society’s Leroy P. Steele Prize in 1983 and on 13 November 1990 the National Medal of Science from President George H. W. Bush, “for his leadership in the theory of recursion and effective computability.” In 1981 he published his own history of the field, “Origins of Recursive Function Theory,” in the Annals of the History of Computing.

He remained a mountaineer. In 1949, Mac Lane recalled, Kleene, Mac Lane and a third climber set out to climb every peak of New Hampshire’s Presidential Range; caught in a thunderstorm on Mount Madison, Kleene called out: “Get down; it’s lightning.” The philosopher Daniel Dennett’s Philosophical Lexicon honoured him with the maxim “Kleeneness is next to Gödelness.” Kleene died of pneumonia in Madison on 25 January 1994, aged 85.