Dana Scott

Dana Stewart Scott
Born	(1932-10-11) October 11, 1932 Berkeley, California
Education	University of California, Berkeley (BA) Princeton University (MA, PhD)
Known for	Automata theory Cartesian monoid Logic of Computable Functions Semantics of programming languages Modal μ-calculus Nondeterministic finite automaton Scott domain Scott encoding Scott information system Scott topology Scott's trick Scott-Montague semantics Scott–Potter set theory Scott–Strachey semantics Rabin–Scott powerset construction
Awards	Leroy P. Steele Prize (1972) Turing Award (1976) Tarski Lectures (1989) Harold Pender Award (1990) Gödel Lecture (1991) Rolf Schock Prize (Logic and Philosophy) (1997) Bolzano Medal (2001) Sobolev Gold Medal (2009) Barwise Prize (2025)
Scientific career
Fields	Computer science Mathematics Philosophy
Workplaces	University of Chicago University of California, Berkeley Stanford Princeton University University of Oxford Carnegie Mellon University
Thesis	Convergent Sequences of Complete Theories (1958)
Doctoral advisor	Alonzo Church
Doctoral students	Jack Copeland Michael Fourman Kenneth Kunen Angus Macintyre Peter Mosses Roy Dyckhoff Ketan Mulmuley Marko Petkovšek Fred S. Roberts David Turner Martin Davies Krister Segerberg Andrej Bauer Joseph Almog

Dana Stewart Scott (born October 11, 1932) is a retired American logician. Along with Michael O. Rabin he received the 1976 ACM Turing Award for their joint work on automata theory. He has made seminal contributions to automata theory, modal logic, set theory, and the theory of programming languages. He created domain theory, a branch of mathematics that provides a foundation for the theory of programming languages and computability.

Early life and education

Dana Stewart Scott was born on October 11, 1932, in Berkeley, California. He completed his undergraduate education at the University of California, Berkeley, receiving a Bachelor of Arts in 1954. He then pursued graduate studies in mathematics at Princeton University, where he held a Bell Telephone Fellowship from 1956 to 1957. Scott earned his Ph.D. in 1958 under the supervision of the mathematical logician Alonzo Church, with a dissertation titled Convergent Sequences of Complete Boolean Algebras.

Solomon Feferman writes of this period :

Scott began his studies in logic at Berkeley in the early 50s while still an undergraduate. His unusual abilities were soon recognized and he quickly moved on to graduate classes and seminars with Tarski and became part of the group that surrounded him, including me and Richard Montague; so it was at that time that we became friends. Scott was clearly in line to do a Ph. D. with Tarski, but they had a falling out for reasons explained in our biography of Tarski. Upset by that, Scott left for Princeton where he finished with a Ph. D. under Alonzo Church. But it was not long before the relationship between them was mended to the point that Tarski could say to him, "I hope I can call you my student," and rightly so: not only did Scott's thesis deal with a problem that had been proposed by Tarski, but all of Scott's work is in the best Tarskian tradition of breadth, rigor, clarity of exposition and clarity of purpose.

During the summer of 1957, while a graduate student, Scott worked as a research intern at IBM Research in Yorktown Heights, New York. There he began a collaboration with Michael O. Rabin, building upon work by Stephen Cole Kleene, John Myhill, and Anil Nerode. Their joint 1959 paper, "Finite Automata and Their Decision Problem", introduced the concept of nondeterministic finite automata, for which both authors later received the 1976 Turing Award.

Academic career

Chicago and Berkeley (1958–1963)

After completing his doctorate in 1958, Scott served as an instructor at the University of Chicago until 1960. He subsequently joined the faculty at the University of California, Berkeley, serving as an assistant professor and later associate professor from 1960 to 1963, during which time he was also appointed a Miller Institute Research Fellow (1960–1961) at Berkeley, and involved himself with classical issues in mathematical logic, especially set theory and Tarskian model theory. He proved that the axiom of constructibility is incompatible with the existence of a measurable cardinal, a result considered seminal in the evolution of set theory.

During this period he started supervising Ph.D. students, such as James Halpern (Contributions to the Study of the Independence of the Axiom of Choice) and Edgar Lopez-Escobar (Infinitely Long Formulas with Countable Quantifier Degrees).

Modal and tense logic

Scott also began working on modal logic in this period, beginning a collaboration with John Lemmon, who moved to Claremont, California, in 1963. Scott was especially interested in Arthur Prior's approach to tense logic and the connection to the treatment of time in natural-language semantics, and began collaborating with Richard Montague (Copeland 2004), whom he had known from his days as an undergraduate at Berkeley. Later, Scott and Montague independently discovered an important generalisation of Kripke semantics for modal and tense logic, called Scott-Montague semantics (Scott 1970).

John Lemmon and Scott began work on a modal-logic textbook that was interrupted by Lemmon's death in 1966. Scott circulated the incomplete monograph amongst colleagues, introducing a number of important techniques in the semantics of model theory, most importantly presenting a refinement of the canonical model that became standard, and introducing the technique of constructing models through filtrations, both of which are core concepts in modern Kripke semantics (Blackburn, de Rijke, and Venema, 2001). Scott eventually published the work as An Introduction to Modal Logic (Lemmon & Scott, 1977).

Stanford, Amsterdam and Princeton, 1963–1972

Following an initial observation of Robert Solovay, Scott formulated the concept of Boolean-valued model, as Solovay and Petr Vopěnka did likewise at around the same time. In 1967, Scott published a paper, A Proof of the Independence of the Continuum Hypothesis, in which he used Boolean-valued models to provide an alternate analysis of the independence of the continuum hypothesis to that provided by Paul Cohen. This work led to the award of the Leroy P. Steele Prize in 1972.

University of Oxford, 1972–1981

Scott took up a post as Professor of Mathematical Logic on the Philosophy faculty of the University of Oxford in 1972. He was member of Merton College while at Oxford and is now an Honorary Fellow of the college.

Semantics of programming languages

This period saw Scott working with Christopher Strachey, and the two managed, despite administrative pressures, to do work on providing a mathematical foundation for the semantics of programming languages, the work for which Scott is best known. Together, their work constitutes the Scott–Strachey approach to denotational semantics, an important and seminal contribution to theoretical computer science. One of Scott's contributions is his formulation of domain theory, allowing programs involving recursive functions and looping-control constructs to be given denotational semantics. Additionally, he provided a foundation for the understanding of infinitary and continuous information through domain theory and his theory of information systems.

Scott's work of this period led to the bestowal of:

• The 1990 Harold Pender Award for his application of concepts from logic and algebra to the development of mathematical semantics of programming languages;
• The 1997 Rolf Schock Prize in logic and philosophy from the Royal Swedish Academy of Sciences for his conceptually oriented logical works, especially the creation of domain theory, which has made it possible to extend Tarski's semantic paradigm to programming languages as well as to construct models of Curry's combinatory logic and Church's calculus of lambda conversion; and
• The 2001 Bolzano Prize for Merit in the Mathematical Sciences by the Czech Academy of Sciences
• The 2007 EATCS Award for his contribution to theoretical computer science.

Carnegie Mellon University, 1981–2003

At Carnegie Mellon University, Scott proposed the theory of equilogical spaces as a successor theory to domain theory; among its many advantages, the category of equilogical spaces is a cartesian closed category, whereas the category of domains is not. In 1994, he was inducted as a Fellow of the Association for Computing Machinery. In 2012 he became a fellow of the American Mathematical Society.

Bibliography

• With Michael O. Rabin, 1959. Finite Automata and Their Decision Problem. doi:10.1147/rd.32.0114
• 1967. A proof of the independence of the continuum hypothesis. Mathematical Systems Theory 1:89–111.
• 1970. 'Advice on modal logic'. In Philosophical Problems in Logic, ed. K. Lambert, pages 143–173.
• With John Lemmon, 1977. An Introduction to Modal Logic. Oxford: Blackwell.
• Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M. W.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications. Vol. 93. Cambridge University Press. ISBN 978-0-521-80338-0.

See also

• List of pioneers in computer science

Further reading

• Blackburn, de Rijke and Venema (2001). Modal logic. Cambridge University Press.
• Jack Copeland (2004). Arthur Prior. In the Stanford Encyclopedia of Philosophy.
• Feferman, Anita Burdman; Feferman, Solomon (2004). Alfred Tarski: Life and Logic. Cambridge University Press. ISBN 978-0-521-80240-6. OCLC 54691904.
• Feferman, Solomon (2006). "Tarski's influence on computer science". Logical Methods in Computer Science. 2 (3): 1–13. doi:10.2168/LMCS-2(3:6)2006.
• Joseph E. Stoy (1977). Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press. ISBN 978-0-262-19147-0

External links

• Official website
• DOMAIN 2002 Workshop on Domain Theory — held in honor of Scott's 70th birthday.
• Dana Scott at the Mathematics Genealogy Project
• Dana Scott interviewed by Gordon Plotkin, as part of the Association for Computing Machinery series of interviews of Turing award winners: Part 1 (Nov 12, 2020) Part 2 (Dec 29, 2020) Part 3 (Jan 12, 2021) Part 4 (Feb 18, 2021)
• Selected papers of Dana S. Scott