1976 达纳·斯科特

shiyi18

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.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
VIDEO INTERVIEW
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. In 1959, while attending a summer session for promising mathematicians, he met Michael Rabin and the two of them 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.

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



Dana S Scott


出生地：美国加州伯克利
1932年10月11日，美国加州伯克利。


教育经历。
文学士（加州大学伯克利分校，1954年）；博士（普林斯顿大学，1958年）。


工作经历：芝加哥大学（讲师，1958年）。
芝加哥大学（讲师，1958-1960）；加州大学伯克利分校（数学助理教授，1960-1962；数学副教授，1962-1963）；斯坦福大学（逻辑和数学副教授，1963-1967，逻辑和数学教授，1967-1969）；阿姆斯特丹大学（数学客座教授，1968-1969）。普林斯顿大学（哲学和数学教授，1969-1972）；牛津大学（数理逻辑教授，1972-1981）；卡内基梅隆大学（计算机科学、数理逻辑和哲学的大学教授，1981-1989，计算机科学的希尔曼教授，1989-2003，2003年起成为名誉教授）；奥地利林茨大学（Osterreich大学教授，符号计算和逻辑，1992-1993）。


荣誉和奖项。
美国数学学会LeRoy P. Steele奖（1972年）；ACM图灵奖，与Michael Rabin（1976年）；宾夕法尼亚大学Harold Pender奖（1990年）；瑞典皇家科学院Rolf Schock逻辑与哲学奖（1997年）；捷克科学院Bolzano数学科学奖（2001年）；欧洲理论计算机科学协会（EATCS）奖（2007）；俄罗斯科学院Sobolev数学研究所金奖（2009）。他是美国艺术与科学学院、英国学院、芬兰科学与文学学院、纽约科学院、美国国家科学院、欧洲科学院的成员；也是ACM的研究员。



DANA STEWART SCOTT DL作者简介链接
美国 - 1976年
参考文献
与迈克尔-O-拉宾（Michael O. Rabin）共同发表论文《有限自动机及其决策问题》，提出了非确定性机器的概念，该概念已被证明是一个非常有价值的概念。他们（斯科特和拉宾）的经典论文一直是这个领域后续工作的灵感来源。

简短注释的
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
采访视频
达纳-斯科特是国际公认的数学逻辑学家，他的工作横跨计算机科学、数学和哲学。他对自动机理论、模态逻辑、模型理论、集合理论和编程语言理论做出了开创性的贡献。他对当代逻辑学做出了根本性的贡献，并因创建领域理论而闻名，领域理论是数学的一个分支，对分析计算机编程语言至关重要。

斯科特的工作具有高度的理论性，在这有限的篇幅中不可能对其进行全面的描述。或许可以用他的图灵奖演讲的导言中对他的兴趣的描述作为替代。

长期以来，逻辑学一直对某些问题的答案在原则上是否可计算感兴趣，因为其结果对形式化的可能性有所限制。最近，通过复杂性理论的发展，决策方法的效率的精确比较已经成为可能。然而，这些都是对逻辑的应用，而一个大问题是逻辑的方法对于可计算性理论的更多应用部分是否有另一个方向的意义。编程语言提供了一个明显的机会，因为它们的句法形式化已经很先进；然而，语义理论很难说是完整的。虽然我们有很多例子，但我们仍然要对这些疑问给出广泛的数学答案。什么是机器？什么是可计算过程？一台机器如何(或多好地)模拟一个过程？程序自然会进入对过程的描述。

那么，对程序确切含义的定义要求我们解释什么是计算的对象(在某种程度上，问题的静态)，以及它们如何被转化(动态)。到目前为止，这些理论......只形式化了该领域的一部分，而且也许过多地集中在有限状态和代数方面。看来，对更高层次程序特征的理解使我们涉及到无限的对象，并迫使我们通过几个层次的解释，从概念性的想法到最终在真实机器上的模拟。如果我们能找到正确的抽象概念来表示必要的结构，这些层次就能在数学上变得精确。

1932年10月11日，斯科特出生于加州伯克利，在加州大学伯克利分校学习哲学和逻辑。他善于学习，并迅速开始参加研究生水平的课程和研讨会。1954年毕业时获得学士学位，他来到普林斯顿大学，并于1958年在阿隆佐-丘奇的指导下完成博士学位。

完成博士学业后，他被任命为芝加哥大学的讲师，并一直在那里工作到1960年。1959年，在参加一个有前途的数学家的暑期班时，他遇到了迈克尔-拉宾，他们两人做了一些工作，导致他们发表了论文（有限自动机及其决策问题）[1]，使他们都获得了图灵奖。这篇论文提出了非确定性机器的概念，与标准的图灵机不同，在程序的每一步可能有几种不同的 "指令 "被执行。

计算复杂性理论是研究在一组特定的资源条件下，如时间（步骤数）、可用的内存、通信的限制、处理器的数量等，可能计算出什么。计算复杂性理论不是专注于一个单一的算法并分析其要求，而是研究一个特定任务的所有可能算法，并将这些任务按必须使用的资源分配到不同的复杂性类别。正如图灵奖引文所示，斯科特和拉宾的非确定性机器的概念在这个研究领域被证明是非常有成效的。

斯科特不仅因其在复杂性方面的工作而闻名，而且还因其对程序属性和语言定义的研究而受到好评--通常以编程语言的语义学或指称语义学为名。在加州大学伯克利分校、斯坦福大学和普林斯顿大学工作后，斯科特于1972年转到牛津大学担任数学逻辑教授。在那里，他与Christopher Strachey紧密合作，为编程语言的语义学提供了一个数学基础。这个斯科特-斯特拉奇语义学，最初被称为，已被证明是理论计算机科学中最有影响力的作品之一。斯科特的主要贡献之一是他的理论工作，使循环和递归函数这些困难的课题能够被纳入这个指称语义结构中。虽然对于典型的计算机程序员（他们在程序中使用这些结构）来说，这些结构的分析背后的理论工作并不容易，这在一定程度上说明了斯科特的能力，他能够同时发展这个语义学领域和他早期的自动机成果--理论计算机科学的两个主要领域，当其中一个被认为是单独的伟大成就。

斯科特在牛津大学呆了九年，但在1981年被吸引回美国，接受卡内基梅隆大学计算机科学、数学逻辑和哲学的大学教授职位。1989年，他在同一机构担任了著名的希尔曼计算机科学教授的职位，并在那里一直工作到2003年退休。他没有安于现状，而是再次处理了几个困难的理论项目。在试图为编程语言，特别是函数式语言定义指称语义时，他提出了等价空间的理论，作为领域理论的替代。虽然很难用几个字来描述，但此举使他再次将一个狭窄的理论课题拓宽为一个更有力量的课题，以描述理论家们感兴趣的课题。特别是它使阿尔弗雷德-塔斯基的早期工作得以扩展，适用于编程语言，以及建立在阿朗佐-丘奇的λ计算的工作之上。

在他的学术生涯中，他指导了大约50名博士生和许多其他研究生项目。

关于他的生活，特别是他的工作的进一步信息，可以在他的图灵奖演讲（这里）和他的书目选集中所列的作品中找到。

语录。

"在你年轻的时候尽可能多地学习，因为以后的生活会变得太忙。"

"试着把数学看作是一门实验科学。