Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

. One of the students of

Alonzo Church Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...

, Kleene, along with

Rózsa Péter Rózsa Péter, born Rózsa Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician. She is best known as the "founding mother of recursion theory". Early life and education Péter was born in Budapest, ...

Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...

Emil Post Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory. Life Post was born in Augustów, Suwałki Gove ...

, and others, is best known as a founder of the branch of

mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

known as

recursion theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

, which subsequently helped to provide the foundations of

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

. Kleene's work grounds the study of

computable function Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...

s. A number of mathematical concepts are named after him:

Kleene hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define t ...

Kleene algebra In mathematics, a Kleene algebra ( ; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator. It generalizes the operations known from regular expressions. Definition Various ine ...

, the

Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid ...

(Kleene closure),

Kleene's recursion theorem In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 ...

and the

Kleene fixed-point theorem In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following: :Kleene Fixed-Point Theorem. Suppose (L, \sqsubseteq) is a directed-complete pa ...

. He also invented

regular expressions A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" o ...

in 1951 to describe McCulloch-Pitts neural networks, and made significant contributions to the foundations of mathematical

intuitionism In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...

Biography

Kleene was awarded a bachelor's degree from

Amherst College Amherst College ( ) is a private liberal arts college in Amherst, Massachusetts. Founded in 1821 as an attempt to relocate Williams College by its then-president Zephaniah Swift Moore, Amherst is the third oldest institution of higher educatio ...

in 1930. He was awarded a Ph.D. in mathematics from

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

in 1934, where his thesis, entitled ''A Theory of Positive Integers in Formal Logic'', was supervised by

. In the 1930s, he did important work on Church's

lambda calculus Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...

. In 1935, he joined the mathematics department at the

University of Wisconsin–Madison A university () is an educational institution, institution of higher education, higher (or Tertiary education, tertiary) education and research which awards academic degrees in several Discipline (academia), academic disciplines. Universities ty ...

, where he spent nearly all of his career. After two years as an instructor, he was appointed assistant professor in 1937. While a visiting scholar at the

Institute for Advanced Study The Institute for Advanced Study (IAS), located in Princeton, New Jersey, in the United States, is an independent center for theoretical research and intellectual inquiry. It has served as the academic home of internationally preeminent scholar ...

in Princeton, 1939–1940, he laid the foundation for

, an area that would be his lifelong research interest. In 1941, he returned to Amherst College, where he spent one year as an associate professor of mathematics. During

World War II World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...

, Kleene was a

lieutenant commander Lieutenant commander (also hyphenated lieutenant-commander and abbreviated Lt Cdr, LtCdr. or LCDR) is a commissioned officer rank in many navies. The rank is superior to a lieutenant and subordinate to a commander. The corresponding rank i ...

in the

United States Navy The United States Navy (USN) is the maritime service branch of the United States Armed Forces and one of the eight uniformed services of the United States. It is the largest and most powerful navy in the world, with the estimated tonnage ...

. He was an instructor of navigation at the U.S. Naval Reserve's Midshipmen's School in New York, and then a project director at the

Naval Research Laboratory The United States Naval Research Laboratory (NRL) is the corporate research laboratory for the United States Navy and the United States Marine Corps. It was founded in 1923 and conducts basic scientific research, applied research, technological ...

Washington, D.C. ) , image_skyline = , image_caption = Clockwise from top left: the Washington Monument and Lincoln Memorial on the National Mall, United States Capitol, Logan Circle, Jefferson Memorial, White House, Adams Morgan, ...

In 1946, Kleene returned to the University of Wisconsin-Madison, becoming a full professor in 1948 and the Cyrus C. MacDuffee professor of mathematics in 1964. He served two terms as the Chair of the Department of Mathematics and one term as the Chair of the Department of Numerical Analysis (later renamed the Department of Computer Science). He also served as Dean of the College of Letters and Science in 1969–1974. During his years at the University of Wisconsin he was thesis advisor to 13 Ph.D. students. He retired from the University of Wisconsin in 1979. In 1999 the mathematics library at the University of Wisconsin was renamed in his honor. Kleene's teaching at Wisconsin resulted in three texts in

, Kleene (1952, 1967) and Kleene and Vesley (1965). The first two are often cited and still in print. Kleene (1952) wrote alternative proofs to the

Gödel's incompleteness theorems Gödel's incompleteness theorems are two theorems of mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research i ...

that enhanced their canonical status and made them easier to teach and understand. Kleene and Vesley (1965) is the classic American introduction to

intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...

and mathematical

. Kleene served as president of the

Association for Symbolic Logic The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is ...

, 1956–1958, and of the International Union of History and Philosophy of Science, 1961. The importance of Kleene's work led to Daniel Dennett coining the saying, published in 1978, that "Kleeneness is next to Gödelness." In 1990, he was awarded the

National Medal of Science The National Medal of Science is an honor bestowed by the President of the United States to individuals in science and engineering who have made important contributions to the advancement of knowledge in the fields of behavioral and social scienc ...

. Kleene and his wife Nancy Elliott had four children. He had a lifelong devotion to the family farm in Maine. An avid mountain climber, he had a strong interest in nature and the

environment Environment most often refers to: __NOTOC__ * Natural environment, all living and non-living things occurring naturally * Biophysical environment, the physical and biological factors along with their chemical interactions that affect an organism or ...

, and was active in many

conservation Conservation is the preservation or efficient use of resources, or the conservation of various quantities under physical laws. Conservation may also refer to: Environment and natural resources * Nature conservation, the protection and managem ...

causes.

Legacy

At each conference of the

Symposium on Logic in Computer Science The ACM–IEEE Symposium on Logic in Computer Science (LICS) is an annual academic conference on the theory and practice of computer science in relation to mathematical logic. Extended versions of selected papers of each year's conference appear i ...

the Kleene award, in honour of Stephen Cole Kleene, is given for the best student paper.

Selected publications

* 1935. * 1935. * 1935. * 1936. * 1936. * 1938. * 1943. * 1951. * 1952.
Introduction to Metamathematics.
' New York: Van Nostrand. (Ishi Press: 2009 reprint). * 1956. * 1965 (with Richard Eugene Vesley). ''The Foundations of Intuitionistic Mathematics''. North-Holland. * 1967.
Mathematical Logic.
'

John Wiley & Sons John Wiley & Sons, Inc., commonly known as Wiley (), is an American multinational publishing company founded in 1807 that focuses on academic publishing and instructional materials. The company produces books, journals, and encyclopedias, in p ...

. Dover reprint, 2002. . * 1981. "Origins of Recursive Function Theory" in
Annals of the History of Computing 3
'' No. 1. * 1987.

Notes

References

External links

*
Biographical memoir
– by

Saunders Mac Lane Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville ...

Kleene bibliography
* – Interview with Kleene and

John Barkley Rosser John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem, in lambda calculus. He also developed what is now called the " Rosser si ...

about their experiences at Princeton * {{DEFAULTSORT:Kleene, Stephen Cole American computer scientists American logicians Amherst College alumni Computability theorists Educators from Hartford, Connecticut Institute for Advanced Study visiting scholars Intuitionism National Medal of Science laureates Princeton University alumni University of Wisconsin–Madison faculty 1909 births 1994 deaths 20th-century American mathematicians Mathematicians from Connecticut