Stephen Cole Kleene was an
AmericanThe United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematicianA mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
who helped lay the foundations for theoretical
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. One of many distinguished students of
Alonzo ChurchAlonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
, Kleene, along with
Alan TuringAlan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
, Emil Post, and others, is best known as a founder of the branch of
mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
known as
recursion theoryComputability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
. Kleene's work grounds the study of which functions are
computableComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
. A number of mathematical concepts are named after him: Kleene hierarchy,
Kleene algebraIn mathematics, a Kleene algebra is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan's laws , additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene algebras are subclasses of Ockham algebras...
, the
Kleene starIn mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
(Kleene closure),
Kleene's recursion theoremIn computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions...
and the
Kleene fixpoint theoremIn the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following:...
. He also invented regular expressions, and was a leading American advocate of mathematical intuitionism.
Kleene pronounced his last name ˈkleɪniː . Commonplace mispronunciations include /ˈkliːniː/ and /ˈkliːn/. (His son, Ken Kleene, wrote: "As far as I am aware this pronunciation is incorrect in all known languages. I believe that this novel pronunciation was invented by my father.")
Biography
Kleene was awarded the BA degree from
Amherst CollegeAmherst College is a private liberal arts college located in Amherst, Massachusetts, United States. Amherst is an exclusively undergraduate four-year institution and enrolled 1,744 students in the fall of 2009...
in 1930. He was awarded the Ph.D. in mathematics from
Princeton UniversityPrinceton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
in 1934. His thesis, entitled A Theory of Positive Integers in Formal Logic, was supervised by
Alonzo ChurchAlonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
. In the 1930s, he did important work on Church's
lambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
. In 1935, he joined the mathematics department at the
University of Wisconsin–MadisonThe University of Wisconsin–Madison is a public research university located in Madison, Wisconsin, United States. Founded in 1848, UW–Madison is the flagship campus of the University of Wisconsin System. It became a land-grant institution in 1866...
, 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 StudyThe Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postgraduate center for theoretical research and intellectual inquiry. It was founded in 1930 by Abraham Flexner...
in Princeton, 1939–40, he laid the foundation for
recursion theoryComputability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, 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 IIWorld War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
, Kleene was a lieutenant commander in the
United States NavyThe United States Navy is the naval warfare service branch of the United States Armed Forces and one of the seven uniformed services of the United States. The U.S. Navy is the largest in the world; its battle fleet tonnage is greater than that of the next 13 largest navies combined. The U.S...
. He was an instructor of navigation at the U.S. Naval Reserve's Midshipmen's School in
New YorkNew York is a state in the Northeastern region of the United States. It is the nation's third most populous state. New York is bordered by New Jersey and Pennsylvania to the south, and by Connecticut, Massachusetts and Vermont to the east...
, and then a project director at the Naval Research Laboratory in
Washington, D.C.Washington, D.C., formally the District of Columbia and commonly referred to as Washington, "the District", or simply D.C., is the capital of the United States. On July 16, 1790, the United States Congress approved the creation of a permanent national capital as permitted by the U.S. Constitution....
In 1946, Kleene returned to
WisconsinWisconsin is a U.S. state located in the north-central United States and is part of the Midwest. It is bordered by Minnesota to the west, Iowa to the southwest, Illinois to the south, Lake Michigan to the east, Michigan to the northeast, and Lake Superior to the north. Wisconsin's capital is...
, becoming a full professor in 1948 and the Cyrus C. MacDuffee professor of mathematics in 1964. He was chair of the Department of Mathematics and Computer Science, 1962–63, and
DeanIn academic administration, a dean is a person with significant authority over a specific academic unit, or over a specific area of concern, or both...
of the College of Letters and Science from 1969 to 1974. The latter appointment he took on despite the considerable student unrest of the day, stemming from the
Vietnam WarThe Vietnam War was a Cold War-era military conflict that occurred in Vietnam, Laos, and Cambodia from 1 November 1955 to the fall of Saigon on 30 April 1975. This war followed the First Indochina War and was fought between North Vietnam, supported by its communist allies, and the government of...
. He retired from the University of Wisconsin in 1979. The mathematics library at the University of Wisconsin was renamed in his honour.
Kleene's teaching at Wisconsin resulted in three texts in
mathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, Kleene (1952, 1967) and Kleene and Vesley (1965), often cited and still in print. Kleene (1952) wrote alternative proofs to the
Gödel's incompleteness theoremsGödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
that enhanced their canonical status and made them easier to teach and understand. Kleene and Vesley (1965) is the classic American introduction to intuitionist logic and mathematics.
Kleene served as president of the
Association for Symbolic LogicThe Association for Symbolic Logic is an international organization of specialists in mathematical logic and philosophical logic—the largest such organization in the world. The ASL was founded in 1936, a crucial year in the development of modern logic, and its first president was Alonzo Church...
, 1956–58, and of the International Union of History and Philosophy of Science, 1961. In 1990, he was awarded the
National Medal of ScienceThe 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 sciences, biology, chemistry, engineering, mathematics and...
.
Kleene and his wife Nancy Elliott had four children. He had a lifelong devotion to the family farm in Maine. An avid mountain climber and
canoeA canoe or Canadian canoe is a small narrow boat, typically human-powered, though it may also be powered by sails or small electric or gas motors. Canoes are usually pointed at both bow and stern and are normally open on top, but can be decked over A canoe (North American English) or Canadian...
ist, he had a strong interest in
natureNature, in the broadest sense, is equivalent to the natural world, physical world, or material world. "Nature" refers to the phenomena of the physical world, and also to life in general...
and the
environmentThe biophysical environment is the combined modeling of the physical environment and the biological life forms within the environment, and includes all variables, parameters as well as conditions and modes inside the Earth's biosphere. The biophysical environment can be divided into two categories:...
, and was active in many
conservationThe conservation movement, also known as nature conservation, is a political, environmental and a social movement that seeks to protect natural resources including animal, fungus and plant species as well as their habitat for the future....
causes.
Important publications
- 1952. Introduction to Metamathematics. Ishi Press International.
- 1956. "Representation of Events in Nerve Nets and Finite Automata" in Automata Studies. Claude Shannon and John McCarthy
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
, eds.
- 1965 (with Richard Eugene Vesley). The Foundations of Intuitionistic Mathematics. North-Holland.
- 1967. Mathematical Logic. John Wiley. Dover reprint, 2001. ISBN 0486425339.
- 1981. "Origins of Recursive Function Theory" in Annals of the History of Computing 3, No. 1.
See also
- Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
- Kleene hierarchy
- Kleene's s-m-n theorem
- Realizability
Realizability is a part of proof theory which can be used to handle information about formulas instead of about the proofs of formulas. A natural number n is said to realize a statement in the language of arithmetic of natural numbers...
- Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...
- Kleene–Rosser paradox
External links