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, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
,
Philosophy
Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. ...
, and
Mathematical Logic
Mathematical logic is the study of 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 forma ...
at
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
; 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 Irish bishop and philosopher George Berkeley. It borders the cities of Oakland and E ...
. His work on
automata theory 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 compu ...
in 1976, while his collaborative work with
Christopher Strachey 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.
Semantics describes the processe ...
. He has worked also on
modal logic
Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend ot ...
,
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, and
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
.
Early career
He received his
B.A. in Mathematics from the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant un ...
, in 1954. He wrote his
Ph.D. thesis on ''Convergent Sequences of Complete Theories'' under the supervision of
Alonzo Church while at
Princeton
Princeton University is a private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the United States and one of the nin ...
, and defended his thesis in 1958.
Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic.
Life
Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
(2005) writes of this period:
After completing his Ph.D. studies, he moved to the
University of Chicago
The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the b ...
, working as an instructor there until 1960. In 1959, he published a joint paper with
Michael O. Rabin, a colleague from Princeton, titled ''Finite Automata and Their Decision Problem'' (Scott and Rabin 1959) which introduced the idea of nondeterministic machines to
automata theory. This work led to the joint bestowal of 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 compu ...
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 relating these classes to each other. A computational problem is a task solved ...
.
University of California, Berkeley, 1960–1963
Scott took up a post as Assistant Professor of Mathematics, back at the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant un ...
, and involved himself with classical issues in
mathematical logic
Mathematical logic is the study of 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 forma ...
, especially
set theory
Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly concern ...
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 (math ...
.
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
Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend ot ...
in this period, beginning a collaboration with
John Lemmon, who moved to
Claremont, California
Claremont () is a suburban city on the eastern edge of Los Angeles County, California, United States, east of downtown Los Angeles. It is in the Pomona Valley, at the foothills of the San Gabriel Mountains. As of the 2010 census it had a popu ...
, 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 contributi ...
's approach to
tense logic 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 formaliz ...
(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 ''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
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 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
, mottoeng = The Lord is my light
, established =
, endowment = £6.1 billion (including colleges) (2019)
, budget = £2.145 billion (2019–20)
, chancellor ...
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 one of the constituent colleges of the University of Oxford in England. Its foundation can be traced back to the 1260s when Walter de Merton, ...
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
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
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 circumscribe the ...
. 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
An information system (IS) is a formal, sociotechnical, organizational system designed to collect, process, store, and distribute information. From a sociotechnical perspective, information systems are composed by four components: task, people ...
.
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
The Royal Swedish Academy of Sciences ( sv, Kungliga Vetenskapsakademien) is one of the royal academies of Sweden. Founded on 2 June 1739, it is an independent, non-governmental scientific organization that takes special responsibility for prom ...
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
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
, 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
A fellow is a concept whose exact meaning depends on context.
In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements.
Within the context of higher education ...
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 member ...
. 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, meeting ...
.
List of Fellows of the American Mathematical Society
retrieved 2013-07-14.
Bibliography
* With Michael O. Rabin, 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 in modal logic'. In ''Philosophical Problems in Logic'', ed. K. Lambert, pages 143–173.
* With John Lemmon, 1977. ''An Introduction to Modal Logic''. Oxford: Blackwell.
*
References
Further reading
*Blackburn, de Rijke and Venema (2001)
''Modal logic''
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
.
* Jack Copeland (2004)
Arthur Prior
In the Stanford Encyclopedia of Philosophy
The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by Stanford University. E ...
.
* Anita Burdman Feferman and Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic.
Life
Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
(2004).
''Alfred Tarski: life and logic''
Cambridge University Press, , .
*Solomon Feferman
Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic.
Life
Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
(2005)
Tarski's influence on computer science
Proc. LICS'05. IEEE Press
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operatio ...
.
*Joseph E. Stoy (1977). ''Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory''. MIT Press
The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts (United States). It was established in 1962.
History
The MIT Press traces its origins back to 1926 when MIT publ ...
.
External links
*
*
DOMAIN 2002 Workshop on Domain Theory
' — held in honor of Scott's 70th birthday.
*
*
* Dana Scott interviewed by Gordon Plotkin, as part 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 member ...
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)
{{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
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
Topologists
Turing Award laureates
University of Chicago faculty
University of California, Berkeley College of Letters and Science faculty
Tarski lecturers
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
Gödel Lecturers