Stephen Kleene

Stephen Cole Kleene

Mathematician and logician · 1909–1994 · United States

Kleene helped turn questions about effective calculation into a systematic mathematical discipline. His work also connects two ways of describing a pattern: an expression that defines a set of strings and a finite machine that recognizes them. Neither contribution should be inflated into the claim that every pattern matcher or programming language descends from one inventor.

Career and research context

Born in Hartford on 5 January 1909, Kleene graduated from Amherst in 1930 and completed his Princeton doctorate under Alonzo Church in 1934. Much of his subsequent career was at Wisconsin. His books include Introduction to Metamathematics (1952) and Mathematical Logic (1967). With Richard Vesley he published The Foundations of Intuitionistic Mathematics in 1965. The differently titled 1969 monograph Formalized Recursive Functionals and Formalized Realizability was Kleene's own work. MacTutor biography, NAS memoir and bibliography.

Kleene's research covered recursive functions, effective ordinals, hierarchies of definability, and realizability interpretations of intuitionistic mathematics. These are related subjects with distinct definitions, not interchangeable names for running a recursive function in software. His automata investigation appeared as a RAND report in 1951 and subsequently as a chapter in Automata Studies in 1956. Its motivating nerve nets were formal models, not modern trained neural networks. Original RAND report.

An algebra of languages

A language is a set of finite strings over a specified alphabet. For languages A and B, union permits either alternative; concatenation forms xy with x in A and y in B; A* permits any finite number of concatenated members of A, including zero. Consequently the empty string belongs to A*, even when A itself is empty. These definitions determine membership, not an implementation's search order.

Classical regular expressions also need base cases for the empty language and empty string. Their expressive power equals that of finite automata. Features called regular expressions in programming products may add backreferences or other operations outside this classical class. A finite automaton can count modulo a fixed number. It cannot remember an arbitrarily large exact count for a later comparison. Thus “regular expressions cannot count” is too crude.

Here is an original worked example. Recognize binary strings with an even number of 1s and an even number of 0s. Use four states, E/E, E/O, O/E, O/O, where the first component records 1-parity and the second 0-parity. Start and accept at E/E. Reading 1 toggles the first component; reading 0 toggles the second. For 1010 the trace is:

Prefix	State
empty	E/E
1	O/E
10	O/O
101	E/O
1010	E/E

The machine accepts. It has processed an arbitrarily long input while retaining only two bits of relevant history. Finite memory is sufficient because exact counts are unnecessary.

In contrast, suppose a machine with k states recognizes all strings 0^n1^n. Among prefixes with zero through k zeros, two must leave the same state. Appending the number of ones needed by the shorter prefix would then make the machine respond identically to one balanced and one unbalanced string. That contradiction proves no such finite automaton exists. This is a teaching proof about the classical model, not a claim about every software regex extension.

Computability is different from cost

Primitive recursion defines a new value using previously defined values and a bounded recursion on a natural number. Unbounded minimization searches for the least witness satisfying a computable test. If no witness exists, search may continue forever. The resulting partial function is undefined there; it does not return a special answer called infinity.

Equivalence between precisely specified models, such as partial recursive functions and Turing-machine computations, is a theorem. Identifying this formal class with informal effective calculability is the Church–Turing thesis. Neither statement establishes a practical runtime bound.

For a program e, input x, and finite step bound t, let H(e,x,t) mean that e halts within t steps. This predicate is decidable by bounded simulation. Halting is expressed by ∃t H(e,x,t), so it has a Σ⁰₁ definition. Totality is expressed by ∀x∃t H(e,x,t), a Π⁰₂ definition. Quantifier blocks classify definability, not seconds or memory consumption. In the standard arithmetical hierarchy, computable sets are Δ⁰₁; identifying all decidable predicates with bounded-arithmetic Δ⁰₀ formulas is incorrect. Recursive Functions, sections 3.3 and 3.6.

Exercises

1. Trace the four-state parity machine on 110010. Then remove the requirement on the number of zeros. Construct the smaller machine and explain why its information is sufficient.
2. Let L = {ab, ba}. List every string in L* of length at most four. Does L* contain aba or abba? Explain why applying star to a set differs from allowing its letters in any order.
3. Consider a routine that searches n = 0,1,2,... for n² = x, with x a nonnegative integer. Trace x = 9 and x = 10. Modify the routine so it always decides whether x is a square, and justify termination. Explain why the successful modification does not yield a general halting decider.

Compare your reasoning with the worked solutions

1. The successive states are E/E, O/E, E/E, E/O, E/E, O/E, O/O. There are three ones and three zeros, so the final state rejects. If only 1-parity matters, two states E and O suffice: 1 toggles, while 0 leaves the state unchanged. Starting and accepting in E recognizes the desired language. Keeping exact counts would add unneeded information; deleting both parity bits would make the empty string and 1 indistinguishable.

2. Zero repetitions give the empty string. One repetition gives ab and ba. Two repetitions give abab, abba, baab, and baba. All words in L* have even length, so aba is absent. The word abba is present as ab followed by ba. Star concatenates complete members of L, preserving their internal order. It does not mean “any string over the alphabet {a,b}.”

3. For 9 the tested squares are 0,1,4,9, and the search returns 3. For 10 the original search passes 9, then tests 16,25,... forever. Stop with “no” once n² exceeds x. Squares increase for nonnegative n, so no later value can equal x; n = x+1 is certainly a sufficient finite bound. This uses a special monotonic property of squares. Arbitrary program execution supplies no analogous computable bound after which failure to halt proves permanent nontermination.

Read with care

Read the RAND report's language definitions alongside its finite-state model. Read the recursion literature with a separate checklist: total or partial functions, permitted search operations, and which quantifiers range over numbers. A historical publication date, a formal equivalence theorem, and a claim about practical programming tools answer different questions.