The 1993 Turing Award was presented to Richard E. Stearns and Juris Hartmanis for a seminal paper that created the foundational structure for computational complexity theory. This research established how the difficulty of a problem scales with its input size, a concept that remains essential to modern computer science and algorithmic efficiency today.
Academic Foundations and Early Research
Born in 1936 in Caldwell, Richard Edwin Stearns began his academic trajectory at Carleton College, where he earned a B.A. in mathematics in 1958. He continued his studies at Princeton University, completing a Ph.D. in mathematics in 1961. His doctoral dissertation, supervised by Harold W. Kuhn, addressed the mathematics of three-person cooperative games without side payments.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Contributions to Computational Theory
During his tenure at General Electric from 1961 to 1978, Stearns produced influential work on the formal properties of computing systems. In 1965, he co-authored a paper on the computational complexity of algorithms, which introduced the time hierarchy theorem. His 1967 study on pushdown machines established the decidability of whether deterministic pushdown automata accept regular languages, while his 1968 collaboration with P.M. Lewis II introduced LL parsers, a development that shaped subsequent methodologies in compiler design.
Academic Tenure and Professional Recognition
Stearns served as a university teacher and researcher at the State University of New York at Albany between 1978 and 2000, eventually holding the title of Distinguished Professor. Throughout his career, he held affiliations with New York University and maintained memberships in the Association for Computing Machinery. Beyond the 1993 Turing Award, his career was marked by his 1994 induction as an ACM Fellow and receiving the Frederick W. Lanchester Prize in 1995. Stearns died on August 29, 2026, at the age of 90.
Fast facts
- Born: 1936, Caldwell
- Died: 29 August 2026
- Education: Carleton College, Princeton University
- Key Award: Turing Award (1993)
- Professional Affiliation: General Electric (1961-1978)
- Academic Tenure: State University of New York at Albany (1978-2000)
- Research Field: Computational complexity theory
- Recognition: ACM Fellow (1994)
Questions readers ask
What is Richard E. Stearns known for?
He is recognized for establishing the foundations of computational complexity theory, specifically through his collaborative work on the time hierarchy theorem.
Where did Stearns teach?
He was a distinguished professor at the State University of New York at Albany and held academic ties to New York University.
Achievements
- Turing Award — 1993
- Affiliated with State University of New York at Albany, New York University and General Electric
- Educated at Princeton University and Carleton College
- Worked as computer scientist, engineer and university teacher
