Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of

Computer Science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

Philosophy Philosophy ('love of wisdom' in Ancient Greek) is a systematic study of general and fundamental questions concerning topics like existence, reason, knowledge, Value (ethics and social sciences), value, mind, and language. It is a rational an ...

, and

Mathematical Logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...

; he is now retired and lives in

Berkeley, California Berkeley ( ) is a city on the eastern shore of San Francisco Bay in northern Alameda County, California, United States. It is named after the 18th-century Anglo-Irish bishop and philosopher George Berkeley. It borders the cities of Oakland, Cali ...

. His work on

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to cognitive science and mathematical l ...

earned him the

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...

in 1976, while his collaborative work with

Christopher Strachey Christopher S. Strachey (; 16 November 1916 – 18 May 1975) was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing.F. J. Corbató, et al., T ...

in the 1970s laid the foundations of modern approaches to the

semantics of programming languages In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and oft ...

. He has also worked on

modal logic Modal logic is a kind of logic used to represent statements about Modality (natural language), necessity and possibility. In philosophy and related fields it is used as a tool for understanding concepts such as knowledge, obligation, and causality ...

topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...

, and

category theory Category theory is a general theory of mathematical structures and their relations. It was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Category theory ...

Early career

He received his

B.A. A Bachelor of Arts (abbreviated B.A., BA, A.B. or AB; from the Latin ', ', or ') is the holder of a bachelor's degree awarded for an undergraduate program in the liberal arts, or, in some cases, other disciplines. A Bachelor of Arts degree ...

in Mathematics from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

, in 1954. He wrote his Ph.D. thesis on ''Convergent Sequences of Complete Theories'' under the supervision of

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

while at

Princeton Princeton University is a private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the Unit ...

, and defended his thesis in 1958.

Solomon Feferman Solomon Feferman (December 13, 1928July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. In addition to his prolific technical work in proof theory, computability theory, and set theory, he was known for h ...

(2005) writes of this period: After completing his Ph.D. studies, he moved to the

University of Chicago The University of Chicago (UChicago, Chicago, or UChi) is a Private university, private research university in Chicago, Illinois, United States. Its main campus is in the Hyde Park, Chicago, Hyde Park neighborhood on Chicago's South Side, Chic ...

, working as an instructor there until 1960. In 1959, he published a joint paper with

Michael O. Rabin Michael Oser Rabin (; born September 1, 1931) is an Israeli mathematician, computer scientist, and recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in Breslau, Germany (today Wrocław, in Poland), th ...

, a colleague from Princeton, titled ''Finite Automata and Their Decision Problem'' (Scott and Rabin 1959) which introduced the idea of nondeterministic machines to

. This work led to the joint bestowal of the

on the two, for the introduction of this fundamental concept of

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

University of California, Berkeley, 1960–1963

Scott took up a post as Assistant Professor of Mathematics, back at the

, and involved himself with classical issues in

mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

, especially

set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...

and Tarskian

model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...

. He proved that the

axiom of constructibility The axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as ''V'' = ''L''. The axiom, first investigated by Kurt Gödel, is inconsistent with the pr ...

is incompatible with the existence of a

measurable cardinal In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure (mathematics), measure on a cardinal ''κ'', or more generally on any set. For a 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

in this period, beginning a collaboration with

John Lemmon Edward John Lemmon (1 June 1930 – 29 July 1966) was a British logician and philosopher born in Sheffield, England. He is most well known for his work on modal logic, particularly his joint text with Dana Scott published posthumously (Lemm ...

, who moved to

Claremont, California Claremont () is a suburban city in eastern Los Angeles County, California, United States, east of Los Angeles. It lies in the Pomona Valley at the foothills of the San Gabriel Mountains. As of the 2010 United States Census, 2010 census it had ...

, in 1963. Scott was especially interested in

Arthur Prior Arthur Norman Prior (4 December 1914 – 6 October 1969), usually cited as A. N. Prior, was a New Zealand–born logician and philosopher. Prior (1957) founded tense logic, now also known as temporal logic, and made important contribution ...

's approach to

tense logic In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am ''always'' hungry", "I will ''eventually'' be hungry", or "I will be hungry ''until'' I ...

and the connection to the treatment of time in natural-language semantics, and began collaborating with

Richard Montague Richard Merritt Montague (September 20, 1930 – March 7, 1971) was an American mathematician and philosopher who made contributions to mathematical logic and the philosophy of language. He is known for proposing Montague grammar to formalize th ...

(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 Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André ...

for modal and tense logic, called

Scott-Montague semantics Neighborhood semantics, also known as Scott–Montague semantics, is a formal semantics for modal logics. It is a generalization, developed independently by Dana Scott and Richard Montague, of the more widely known relational semantics for modal l ...

(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 Robert Martin Solovay (born December 15, 1938) is an American mathematician working in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on ''A F ...

, Scott formulated the concept of

Boolean-valued model In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take v ...

, as Solovay and

Petr Vopěnka Petr Vopěnka (16 May 1935 – 20 March 2015) was a Czech people, Czech mathematician. In the early seventies, he developed alternative set theory (i.e. alternative to the classical Cantor theory), which he subsequently developed in a series of ...

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 In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states: Or equivalently: In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...

to that provided by

Paul Cohen Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician, best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was awarded a F ...

. This work led to the award of the

Leroy P. Steele Prize The Leroy P. Steele Prizes are awarded every year by the American Mathematical Society, for distinguished research work and writing in the field of mathematics. Since 1993, there has been a formal division into three categories. The prizes have b ...

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 The University of Oxford is a collegiate university, collegiate research university in Oxford, England. There is evidence of teaching as early as 1096, making it the oldest university in the English-speaking world and the List of oldest un ...

in 1972. He was member of

Merton College Merton College (in full: The House or College of Scholars of Merton in the University of Oxford) is a constituent college of the University of Oxford in England. Its foundation can be traced back to the 1260s when Walter de Merton, chancellor ...

while at Oxford and is now an Honorary Fellow of the college.

Semantics of programming languages

This period saw Scott working with

, 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 In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...

, an important and seminal contribution to

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

. One of Scott's contributions is his formulation of

domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...

, 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 An information system (IS) is a formal, sociotechnical, organizational system designed to collect, process, store, and distribute information. From a sociotechnical perspective, information systems comprise four components: task, people, structu ...

. Scott's work of this period led to the bestowal of: * The 1990

Harold Pender Award The Harold Pender Award, initiated in 1972 and named after founding Dean Harold Pender, is given by the Faculty of the School of Engineering and Applied Science of the University of Pennsylvania to an outstanding member of the engineering profess ...

for his ''application of concepts from logic and algebra to the development of mathematical semantics of programming languages''; * The 1997

Rolf Schock Prize The Rolf Schock Prizes were established and endowed by bequest of philosopher and artist Rolf Schock (1933–1986). The prizes were first awarded in Stockholm, Sweden, in 1993 and, since 2005, are awarded every three years. It is sometimes conside ...

in logic and philosophy from the

Royal Swedish Academy of Sciences The Royal Swedish Academy of Sciences () is one of the Swedish Royal Academies, royal academies of Sweden. Founded on 2 June 1739, it is an independent, non-governmental scientific organization that takes special responsibility for promoting nat ...

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 Bolzano ( ; ; or ) is the capital city of South Tyrol (officially the province of Bolzano), Northern Italy. With a population of 108,245, Bolzano is also by far the largest city in South Tyrol and the third largest in historical Tyrol. The g ...

for Merit in the Mathematical Sciences by the

Czech Academy of Sciences The Czech Academy of Sciences (abbr. CAS, , abbr. AV ČR) was established in 1992 by the Czech National Council as the Czech successor of the former Czechoslovak Academy of Sciences and its tradition goes back to the Royal Bohemian Society of Sc ...

* The 2007

EATCS The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

Award for his contribution to theoretical computer science.

Carnegie Mellon University, 1981–2003

, 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 In category theory, a Category (mathematics), category is Cartesian closed if, roughly speaking, any morphism defined on a product (category theory), product of two Object (category theory), objects can be naturally identified with a morphism defin ...

, whereas the category of domains is not. In 1994, he was inducted as a

Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...

of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

. In 2012 he became a fellow of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

.List of Fellows of the American Mathematical Society
retrieved 2013-07-14.

Bibliography

* With

, 1959. ''Finite Automata and Their Decision Problem''. * 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

, 1977. ''An Introduction to Modal Logic''. Oxford: Blackwell. *

References

External links

* *
DOMAIN 2002 Workshop on Domain Theory
' — held in honor of Scott's 70th birthday. * * * Dana Scott interviewed by

Gordon Plotkin Gordon David Plotkin (born 9 September 1946) is a theoretical computer scientist in the School of Informatics at the University of Edinburgh. Plotkin is probably best known for his introduction of structural operational semantics (SOS) and his ...

, as part of the

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
' {{DEFAULTSORT:Scott, Dana American computer scientists American logicians 1932 births Living people Members of the United States National Academy of Sciences Carnegie Mellon University faculty 1994 fellows of the Association for Computing Machinery Fellows of the American Mathematical Society Fellows of Merton College, Oxford Formal methods people Lattice theorists Mathematical logicians Modal logicians Model theorists Programming language researchers Rolf Schock Prize laureates Semanticists Set theorists American topologists Turing Award laureates University of Chicago faculty University of California, Berkeley College of Letters and Science faculty Princeton University alumni UC Berkeley College of Letters and Science alumni People from Berkeley, California Engineers from California Scientists from California 20th-century American mathematicians 20th-century American engineers 21st-century American engineers 20th-century American scientists 21st-century American scientists 21st-century American mathematicians