Stephen Cole Kleene

Stephen Cole Kleene was an American mathematician and logician and one of the founders of recursion theory, the branch of mathematical logic that studies which functions can be computed by mechanical procedures. His work, developed mainly in the first half of the twentieth century, helped lay the foundations of theoretical computer science and belongs to the tradition of formal logic and mathematical intuitionism.

Born in Hartford, Connecticut, in 1909, he earned a bachelor's degree from Amherst College in 1930. He completed his doctorate at Princeton in 1934 under Alonzo Church, with a thesis on a theory of positive integers in formal logic, and did important work on Church's lambda calculus. From 1935 until his retirement in 1979 he was based at the University of Wisconsin–Madison, where he became a professor and later dean of the College of Letters and Science. During the Second World War he served in the United States Navy. In the 1930s he laid the groundwork for recursion theory, which remained his central research interest for the rest of his life.

His legacy includes several concepts that bear his name, among them the Kleene closure, the Kleene recursion theorem, the Kleene fixed-point theorem and Kleene algebra. In 1951 he introduced regular expressions to describe McCulloch-Pitts neural networks, an idea now central to automata theory and text processing. In intuitionism, his book with Vesley remains a classic American introduction to the subject. His textbooks, especially the one from 1952, offered alternative proofs of Gödel's incompleteness theorems that made them easier to teach and understand.

His influence endures: recursion theory gave a rigorous basis to the notion of computability, and his name appears throughout logic, formal language theory and computer science. He also served as president of the Association for Symbolic Logic and of the International Union of History and Philosophy of Science.