Dana Scott

From Example Problems
Jump to navigation Jump to search

Dana S. Scott (born 1932) is the incumbent Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University. His research career has spanned computer science, mathematics and philosophy, and has been characterised by a marriage of a concern for elucidating fundamental concepts in the manner of informal rigour, 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.

Early career

He received his Bachelor's degree 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. After completing his PhD 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.

University of California, Berkeley, 19601963

Scott took up a post as Assistant Professor of Mathematics, at the University of California, Berkeley, the university of Alfred Tarski, and involved himself with classical issues in mathematical logic, especially set theory and Tarskian model theory.

During this period he started supervising PhD 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.

Stanford, Amsterdam and Princeton, 19631972

In 1967 he published a paper, A proof of the independence of the continuum hypothesis, which introduced 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.

Oxford University, 19721981

Dana Scott took up a post as Professor of Mathematical Logic, in the Philosophy Faculty of Oxford University in 1972.

Semantics of programming languages

This period saw Scott working close to Christopher Strachey, 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, and it is constitutes one of the most deeply influential pieces of work in theoretical computer science, and can perhaps be regarded as founding one of the major schools of computer science. Scott's most major contribution 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:

  • 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 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.

Carnegie Mellon University 19812003

Recently, at CMU in the US, Scott has 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.


  • With Michael O. Rabin, Finite Automata and Their Decision Problem (1959).
  • A proof of the independence of the continuum hypothesis (1967). Mathematical Systems Theory 1:89–111.

External links