A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to Maurice V. Wilkes's profile page
  • go to David Patterson's profile page
  • go to Ole-Johan Dahl 's profile page
  • go to A. J. Perlis 's profile page
  • go to Kristen Nygaard 's profile page
  • go to Richard W. Hamming's profile page
  • go to Yann LeCun's profile page
  • go to Leonard M. Adleman's profile page
  • go to Jeffrey D Ullman's profile page
  • go to Herbert A. Simon's profile page
  • go to Niklaus E. Wirth's profile page
  • go to E. Allen Emerson's profile page
  • go to Judea Pearl's profile page
  • go to Kenneth E. Iverson 's profile page
  • go to Pat Hanrahan's profile page
  • go to Edmund Clarke's profile page
  • go to Ivan Sutherland's profile page
  • go to J. H. Wilkinson 's profile page
  • go to A J Milner 's profile page
  • go to Michael Stonebraker's profile page
  • go to Barbara Liskov's profile page
  • go to Jim Gray 's profile page
  • go to Raj Reddy's profile page
  • go to Michael O. Rabin 's profile page
A.M. TURING AWARD LAUREATES BY...
Dana S Scott

 

BIRTH:

October 11, 1932, Berkeley, California, USA.
 

EDUCATION:

BA (University of California, Berkeley, 1954); PhD (Princeton University, 1958).


EXPERIENCE:

University of Chicago (Instructor,1958-1960); University of California, Berkeley (Assistant Professor of mathematics, 1960-1962; Associate Professor of mathematics, 1962-1963);, Stanford University (Associate Professor of logic and mathematics, 1963-1967, Professor of logic and mathematics, 1967-1969); University of Amsterdam (Visiting Professor of mathematics, 1968-1969); Princeton University (Professor of philosophy and mathematics, 1969-1972); Oxford University (Professor of mathematical logic, 1972-1981); Carnegie Mellon University (University professor of computer science, mathematical logic, and philosophy, 1981-1989, Hillman Professor of Computer Science, 1989-2003, emeritus since 2003); University of Linz, Austria (Osterreich University Professor, symbolic computation and logic,1992-1993).
 

HONORS AND AWARDS:

LeRoy P. Steele Prize, American Mathematical Society (1972); ACM Turing Award, with Michael Rabin (1976); Harold Pender Award, University of Pennsylvania (1990); Rolf Schock Prize in Logic and Philosophy, Royal Swedish Academy of Sciences (1997); Bolzano Medal for Merit in the Mathematical Sciences, Czech Academy of Sciences (2001); European Association for Theoretical Computer Science (EATCS) Award (2007); Russian Academy of Science’s Sobolev Institute of Mathematics Gold Medal (2009). He is a member of the American Academy of Arts and Sciences, British Academy, Finnish Academy of Sciences and Letters, New York Academy of Sciences, US National Academy of Sciences, Academia Europaea; and a fellow of the ACM.

 

Dana Stewart Scott DL Author Profile link

United States – 1976
CITATION

Along with Michael O. Rabin, for their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

Dana Scott is an internationally recognized mathematical logician whose work has spanned computer science, mathematics, and philosophy. He made seminal contributions to automata theory, modal logic, model theory, set theory, and the theory of programming languages. He has made fundamental contributions to contemporary logic and is known for his creation of domain theory, a branch of mathematics that is essential for analyzing computer programming languages.

Scott’s work is highly theoretical and a full description of it is not possible in this limited space. Perhaps an alternate is the description of his interests contained in the introduction to his Turing Award Lecture:

Logic has been long interested in whether answers to certain questions are computable in principle, since the outcome puts bounds on the possibilities of formalization. More recently, precise comparisons in the efficiency of decision methods have become available through the developments in complexity theory. These, however, are applications to logic, and a big question is whether methods of logic have significance in the other direction for the more applied parts of computability theory. Programming languages offer an obvious opportunity as their syntactic formalization is well advanced; however, the semantical theory can hardly be said to be complete. Though we have many examples, we have still to give wide-ranging mathematical answers to these queries: What is a machine? What is a computable process? How (or how well) does a machine simulate a process? Programs naturally enter in giving descriptions of processes.

The definition of the precise meaning of a program then requires us to explain what are the objects of computation (in a way, the statics of the problem) and how they are to be transformed (the dynamics). So far the theories … have formalized only a portion of the field, and there has been perhaps too much concentration on the finite-state and algebraic aspects. It would seem that the understanding of higher-level program features involves us with infinite objects and forces us to pass through several levels of explanation to go from the conceptual ideas to the final simulation on a real machine. These levels can be made mathematically exact if we can find the right abstractions to represent the necessary structures.

Born October 11, 1932, in Berkeley, California, Scott attended the University of California, Berkeley, studying philosophy and logic. He was adept at his studies and rapidly began to attend classes and seminars at the graduate level. Graduating with a BA in 1954, he moved to Princeton University and completed a PhD under the supervision of Alonzo Church in 1958. After completing his Ph.D. studies, he took an appointment at the University of Chicago, as an instructor and remained there until 1960.

Scott discusses the thesis he wrote on infinite dimensional geometry under Alonzo Church at Princeton.

While attend a summer session for promising mathematicians, he and Michael Rabin  did work leading to their publishing of the paper (Finite Automata and Their Decision Problem) [1]  that resulted in them both receiving the Turing Award. This paper introduced the concept of nondeterministic machines in which, unlike the standard Turing Machine, there can be several different possible “instructions” that might be executed at each step of the program.

Scott talks about introducing nondeterministic automata as a grad student summer project with Michael Rabin.

Computational complexity theory is the study of what is possible to calculate given a specific set of resources such as time (number of steps), memory available, limits on communication, the number of processors, etc. Rather than focusing on a single algorithm and analyzing its requirements, computational complexity theory examines all possible algorithms for a specific task and assigning these tasks to different categories of complexity in terms of resources that must be used. As the Turing Award citation indicates, Scott and Rabin’s concept of nondeterministic machines has proved extremely productive in this research area.

Scott is not only known for his work in complexity, but is also well regarded for his research into the study of program properties and language definitions—usually known by the terms semantics of programming languages or denotational semantics. After working at the University of California, Berkley, Stanford University, and Princeton University, Scott moved to take the position of Professor of Mathematical Logic at Oxford University in 1972.

Scott recalls the origins of the computer science department at Stanford.

While there he worked closely with Christopher Strachey to provide a mathematical foundation for the semantics of programming languages. This Scott-Strachey semantics, as it was initially called, has proved to be one of the most influential works in theoretical computer science. One of Scott’s major contributions was the theoretical work that allowed the difficult subjects of loops and recursive functions to be included into this denotational semantic structure. While it may seem elementary to the typical computer programmer (who uses these constructs in programs) the theoretical work behind the analysis of these constructs is anything but easy and it is some indication of Scott’s ability that he was able to develop both this semantics area and his earlier automata results—two major areas of theoretical computer science when one would be considered a grand achievement on its own.

Scott talks about Strachey’s connection to his influential paper on the Logic of Computable Functions.

Scott remained at Oxford for nine years but in 1981 was enticed back to America to accept the position of University Professor of Computer Science, Mathematical Logic, and Philosophy, at Carnegie Mellon University. In 1989 he took the prestigious position of Hillman Professor of Computer Science at the same institution and remained there until his retirement in 2003. Rather than resting on his laurels, he again tackled several difficult theoretical projects. He proposed the theory of equilogical spaces as a replacement for domain theory when attempting to define denotational semantics for programming languages, particularly functional languages. While difficult to describe in a few words, this move enabled him to once again broaden a narrow theoretical subject to one with much more power to describe subjects of interest to theoreticians. In particular it allowed the extension of earlier work by Alfred Tarski to apply to programming languages as well as building on the work of Alonzo Church’s lambda calculus.

During his academic career he has supervised about 50 PhD students and numerous other graduate projects.

Further information on his life and particularly on his work can be found in his Turing Award Lecture (here) and in the works listed in his selected bibliography.

Quotations:

“Learn as much as you can while you are young, since life becomes too busy later.”

“Try to regard mathematics as an experimental science.