Dana Scott

Last updated
Dana Stewart Scott
Scott Dana small.jpg
Born (1932-10-11) October 11, 1932 (age 92)
Berkeley, California
Education UC Berkeley (B.A., 1954) Princeton University (Ph.D., 1958)
Known for
Awards
Scientific career
Fields
Institutions
Thesis Convergent Sequences of Complete Theories  (1958)
Doctoral advisor Alonzo Church
Doctoral students

Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University [1] ; he is now retired and lives in Berkeley, California. His work on automata theory earned him the 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 also worked on modal logic, topology, and category theory.

Contents

Early career

He received his B.A. 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:

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. [2] 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, 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 on the two, for the introduction of this fundamental concept of computational complexity theory.

University of California, Berkeley, 1960–1963

Scott took up a post as Assistant Professor of Mathematics, back at the University of California, 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. [3]

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 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,[ clarification needed ] to do work on providing a mathematical foundation for the semantics of programming languages, the work for which Scott is best known[ opinion ]. 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:

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 [4] 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. [5]

Bibliography

Related Research Articles

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 formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

In computer science, denotational semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects that describe the meanings of expressions from the languages. Other approaches providing formal semantics of programming languages include axiomatic semantics and operational semantics.

<span class="mw-page-title-main">Alfred Tarski</span> Polish–American mathematician (1901–1983)

Alfred Tarski was a Polish-American logician and mathematician. A prolific author best known for his work on model theory, metamathematics, and algebraic logic, he also contributed to abstract algebra, topology, geometry, measure theory, mathematical logic, set theory, and analytic philosophy.

The history of logic deals with the study of the development of the science of valid inference (logic). Formal logics developed in ancient times in India, China, and Greece. Greek methods, particularly Aristotelian logic as found in the Organon, found wide application and acceptance in Western science and mathematics for millennia. The Stoics, especially Chrysippus, began the development of predicate logic.

<span class="mw-page-title-main">Michael O. Rabin</span> Israeli mathematician and computer scientist (born 1931)

Michael Oser Rabin is an Israeli mathematician, computer scientist, and recipient of the Turing Award.

<span class="mw-page-title-main">Solomon Feferman</span> American philosopher and mathematician

Solomon Feferman 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 his contributions to the history of logic and as a vocal proponent of the philosophy of mathematics known as predicativism, notably from an anti-platonist stance.

<span class="mw-page-title-main">Leon Henkin</span> American mathematician

Leon Albert Henkin was an American logician, whose works played a strong role in the development of logic, particularly in the theory of types. He was an active scholar at the University of California, Berkeley, where he made great contributions as a researcher, teacher, as well as in administrative positions. At this university he directed, together with Alfred Tarski, the Group in Logic and the Methodology of Science, from which many important logicians and philosophers emerged. He had a strong sense of social commitment and was a passionate defender of his pacifist and progressive ideas. He took part in many social projects aimed at teaching mathematics, as well as projects aimed at supporting women's and minority groups to pursue careers in mathematics and related fields. A lover of dance and literature, he appreciated life in all its facets: art, culture, science and, above all, the warmth of human relations. He is remembered by his students for his great kindness, as well as for his academic and teaching excellence.

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 often crosses over with, the semantics of mathematical proofs.

<span class="mw-page-title-main">Richard Montague</span> American mathematician (1930–1971)

Richard Merritt Montague 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 the semantics of natural language. As a student of Alfred Tarski, he also contributed early developments to axiomatic set theory (ZFC). For the latter half of his life, he was a professor at the University of California, Los Angeles until his early death, believed to be a homicide, at age 40.

<span class="mw-page-title-main">Samson Abramsky</span> British computer scientist

Samson Abramsky is a British computer scientist who is a Professor of Computer Science at University College London. He was previously the Christopher Strachey Professor of Computing at Wolfson College, Oxford, from 2000 to 2021.

<span class="mw-page-title-main">Robert Lawson Vaught</span> American mathematician

Robert Lawson Vaught was a mathematical logician and one of the founders of model theory.

<span class="mw-page-title-main">Programming language theory</span> Branch of computer science

Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, and linguistics. There are a number of academic conferences and journals in the area.

Edward John Lemmon 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.

A timeline of mathematical logic; see also history of logic.

Formal semantics is the study of grammatical meaning in natural languages using formal concepts from logic, mathematics and theoretical computer science. It is an interdisciplinary field, sometimes regarded as a subfield of both linguistics and philosophy of language. It provides accounts of what linguistic expressions mean and how their meanings are composed from the meanings of their parts. The enterprise of formal semantics can be thought of as that of reverse-engineering the semantic components of natural languages' grammars.

John Charles Chenoweth McKinsey, usually cited as J. C. C. McKinsey, was an American mathematician known for his work on game theory and mathematical logic, particularly, modal logic.

The Alfred Tarski Lectures are an annual distinction in mathematical logic and series of lectures held at the University of California, Berkeley. Established in tribute to Alfred Tarski on the fifth anniversary of his death, the award has been given every year since 1989. Following a 2-year hiatus after the 2020 lecture was not given due to the COVID-19 pandemic, the lectures resumed in 2023.

Anne C. Morel was an American mathematician known for her work in logic, order theory, and algebra. She was the first female full professor of mathematics at the University of Washington.

The Gödel Lecture is an honor in mathematical logic given by the Association for Symbolic Logic, associated with an annual lecture at the association's general meeting. The award is named after Kurt Gödel and has been given annually since 1990.

References

  1. ↑ "Dana S. Scott" . Retrieved 13 October 2024.
  2. ↑ Feferman & Feferman 2004.
  3. ↑ Kanamori, The Higher infinite, p. 44, 49.
  4. ↑ Where here Dana Scott counts the category of domains to be the category whose objects are pointed directed-complete partial orders (DCPOs), and whose morphisms are the strict, Scott-continuous functions
  5. ↑ List of Fellows of the American Mathematical Society, retrieved 2013-07-14.

Further reading

Academic offices
Preceded by President of the DLMPST/IUHPST
1983–1987		Succeeded by
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.