Dana Scott
Encyclopedia
Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science
, Philosophy
, and Mathematical Logic
at Carnegie Mellon University
; he is now retired and lives in Berkeley, California
. His research career has spanned computer science
, mathematics
, and philosophy
, and has been characterized by a marriage of a concern for elucidating fundamental concepts in the manner of informal rigor, with a cultivation of mathematically hard problems that bear on these concepts. His work on automata theory
earned him the ACM Turing Award in 1976, while his collaborative work with Christopher Strachey
in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has worked also on modal logic
, topology
, and category theory
. He is the editor-in-chief of the new journal Logical Methods in Computer Science
.
in Mathematics from the University of California, Berkeley
, in 1954. He wrote his Ph.D. thesis
on Convergent Sequences of Complete Theories under the supervision of Alonzo Church
while at Princeton, and defended his thesis in 1958. Solomon Feferman
(2005) writes of this period:
After completing his Ph.D. studies, he moved to the University of Chicago
, working as an instructor there until 1960. In 1959, he published a joint paper with Michael O. Rabin
, a colleague from Princeton, entitled Finite Automata and Their Decision Problem, which introduced the idea of nondeterministic machines to automata theory
. This work led to the joint bestowal of the Turing Award
on the two, for the introduction of this fundamental concept of computational complexity theory
.
, and involved himself with classical issues in mathematical logic
, especially set theory
and Tarskian model 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). Scott's work as research supervisor has been an important source of his intellectual influence.
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 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).
, 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.
, and the two
managed, despite intense administrative pressures, to oversee a great deal of fundamental 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
; it constitutes one of the most influential pieces of work in theoretical computer science
and can perhaps be regarded as founding one of the major schools of computer science
. One of Scott's largest contributions is his formulation of domain theory
, allowing programs involving recursive functions and looping-control constructs to be given a 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:
, 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
.
Computer science
Computer 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...
, Philosophy
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
, and Mathematical Logic
Mathematical logic
Mathematical 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...
at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
; he is now retired and lives in Berkeley, California
Berkeley, California
Berkeley is a city on the east shore of the San Francisco Bay in Northern California, United States. Its neighbors to the south are the cities of Oakland and Emeryville. To the north is the city of Albany and the unincorporated community of Kensington...
. His research career has spanned computer science
Computer science
Computer 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...
, mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, and philosophy
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
, and has been characterized by a marriage of a concern for elucidating fundamental concepts in the manner of informal rigor, with a cultivation of mathematically hard problems that bear on these concepts. His work on automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
earned him the ACM Turing Award in 1976, while his collaborative work with Christopher Strachey
Christopher Strachey
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has worked also on modal logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
, topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
, and category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. He is the editor-in-chief of the new journal Logical Methods in Computer Science
Logical Methods in Computer Science
Logical Methods in Computer Science is a peer-reviewed journal in theoretical computer science and applied logic conceived in 2004...
.
Early career
He received his BABachelor of Arts
A Bachelor of Arts , from the Latin artium baccalaureus, is a bachelor's degree awarded for an undergraduate course or program in either the liberal arts, the sciences, or both...
in Mathematics from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, in 1954. He wrote his Ph.D. thesis
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
on Convergent Sequences of Complete Theories under the supervision of Alonzo Church
Alonzo Church
Alonzo 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...
while at Princeton, and defended his thesis in 1958. Solomon Feferman
Solomon Feferman
Solomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
(2005) 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 TarskiAlfred TarskiAlfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
and became part of the group that surrounded him, including me and Richard MontagueRichard MontagueRichard Merett Montague was an American mathematician and philosopher.-Career:At the University of California, Berkeley, Montague earned an B.A. in Philosophy in 1950, an M.A. in Mathematics in 1953, and a Ph.D. in Philosophy 1957, the latter under the direction of the mathematician and logician...
; 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. 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”'.
After completing his Ph.D. studies, he moved to the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
, working as an instructor there until 1960. In 1959, he published a joint paper with Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
, a colleague from Princeton, entitled Finite Automata and Their Decision Problem, which introduced the idea of nondeterministic machines to automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
. This work led to the joint bestowal of the Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
on the two, for the introduction of this fundamental concept of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
University of California, Berkeley, 1960–1963
Scott took up a post as Assistant Professor of Mathematics, back at the University of California, BerkeleyUniversity of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, and involved himself with classical issues in mathematical logic
Mathematical logic
Mathematical 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...
, especially set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
and Tarskian model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
.
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). Scott's work as research supervisor has been an important source of his intellectual influence.
Modal and tense logic
Scott also began working on modal logicModal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...
in this period, beginning a collaboration with John Lemmon
John Lemmon
Edward John Lemmon was a logician and philosopher born in Sheffield, UK. He is most well known for his work on modal logic, particularly his joint text with Dana Scott published posthumously ....
, who moved to Claremont, California
Claremont, California
Claremont is a small affluent college town in eastern Los Angeles County, California, United States, about east of downtown Los Angeles at the base of the San Gabriel Mountains. The population as of the 2010 census is 34,926. Claremont is known for its seven higher-education institutions, its...
, in 1963. Scott was especially interested in Arthur Prior
Arthur Prior
Arthur Norman Prior was a noted logician and philosopher. Prior founded tense logic, now also known as temporal logic, and made important contributions to intensional logic, particularly in Prior .-Biography:Prior was entirely educated in New Zealand, where he was fortunate to have come under the...
's approach to tense logic and the connection to the treatment of time in natural-language semantics, and began collaborating with Richard Montague
Richard Montague
Richard Merett Montague was an American mathematician and philosopher.-Career:At the University of California, Berkeley, Montague earned an B.A. in Philosophy in 1950, an M.A. in Mathematics in 1953, and a Ph.D. in Philosophy 1957, the latter under the direction of the mathematician and logician...
(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
Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal logics, and later adapted to intuitionistic logic and other non-classical systems...
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
Kripke semantics
Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke. It was first made for modal logics, and later adapted to intuitionistic logic and other non-classical systems...
(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 modelBoolean-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 values in some fixed complete Boolean...
, as Solovay and Petr Vopěnka
Petr Vopenka
Petr Vopěnka is a Czech mathematician. In the early seventies, he established the Alternative Set Theory , which he subsequently developed in a series of articles and monographs...
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
Continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
to that provided by Paul Cohen
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
. This work led to the award of the Leroy P. Steele Prize in 1972.
Oxford University, 1972–1981
Scott took up a post as Professor of Mathematical Logic on the Philosophy faculty of Oxford University in 1972.Semantics of programming languages
This period saw Scott working closely with Christopher StracheyChristopher Strachey
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
, and the two
managed, despite intense administrative pressures, to oversee a great deal of fundamental 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
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
; it constitutes one of the most influential pieces of work in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
and can perhaps be regarded as founding one of the major schools of computer science
Computer science
Computer 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 Scott's largest contributions is his formulation of domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
, allowing programs involving recursive functions and looping-control constructs to be given a 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 information system
In domain theory, a branch of mathematics and computer science, a Scott information system is a primitive kind of logical deductive system often used as an alternative way of presenting Scott domains.-Definition:...
.
Scott's work of this period led to the bestowal of:
- The 1990 Harold Pender AwardHarold Pender AwardThe 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 profession who has achieved distinction by significant...
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 SciencesRoyal Swedish Academy of SciencesThe Royal Swedish Academy of Sciences or Kungliga Vetenskapsakademien is one of the Royal Academies of Sweden. The Academy is an independent, non-governmental scientific organization which acts to promote the sciences, primarily the natural sciences and mathematics.The Academy was founded on 2...
for his conceptually oriented logical works, especially the creation of domain theory, which has made it possible to extend Tarski's semantical 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 EATCSEATCSThe European Association for Theoretical Computer Science is an international organization with a European focus, founded in 1972...
Award for his contribution to theoretical computer science.
Carnegie Mellon University 1981–2003
At Carnegie Mellon UniversityCarnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
, 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
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
, whereas the category of domains is not. In 1994 he was inducted as a Fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
.
Works by Scott
- With Michael O. RabinMichael O. RabinMichael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
, 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 LemmonJohn LemmonEdward John Lemmon was a logician and philosopher born in Sheffield, UK. He is most well known for his work on modal logic, particularly his joint text with Dana Scott published posthumously ....
, 1977. An Introduction to Modal Logic. Oxford: Blackwell.
Other works
- Blackburn, de Rijke and Venema (2001). Modal logic. Cambridge University Press.
- Jack CopelandJack CopelandBrian Jack Copeland is Professor of Philosophy at the University of Canterbury, Christchurch, New Zealand.Copeland received a BPhil and DPhil from the University of Oxford in philosophy, where he undertook research on modal and non-classical logic.He is the Director of the Turing Archive for the...
(2004). Arthur Prior. In the Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
. - Solomon FefermanSolomon FefermanSolomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
and Anita Burdman Feferman (2004). Alfred Tarski: life and logic. Cambridge University Press, ISBN 0521802407, ISBN 9780521802406. - Solomon FefermanSolomon FefermanSolomon Feferman is an American philosopher and mathematician with major works in mathematical logic.He was born in New York City, New York, and received his Ph.D. in 1957 from the University of California, Berkeley under Alfred Tarski...
(2005). Tarski’s influence on computer science. Proc. LICS'05. IEEE Press. - Joseph E. Stoy (1977). Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press. ISBN 0-262-19147-4
External links
- Dana S. Scott's home page
- DOMAIN 2002 Workshop on Domain Theory – held in honor of Scott's 70th birthday.