人工智能名人堂第26期 | 理论计算机先驱-麦克纳哈特
丘吉尔曾说过，“The longer you can look back, the farther you can look forward. (回顾历史越久远，展望未来就越深远)”，为纪念人工智能领域做出杰出贡献的先辈与开拓者们，鼓励更多后起之秀投身该领域，人工智能国际杂志《IEEE Intelligent Systems》自2006年始至今陆续推选出了60位人工智能专家(参看《诺伯特·维纳奖得主王飞跃 | AI 名人堂，世界人工智能60年60位名人榜》)。德先生自2016年10月31日起，已定期于每周一在微信公众号（D-Technologies）上发布人工智能名人堂60位成员的相关介绍。往期内容可查看延伸阅读。
本期AI名人堂的主人公罗伯特·麦克纳哈特（Robert F. McNaughton）。McNaughton哥伦比亚大学毕业， 哈佛哲学博士。于20世纪50年代转向计算机科学领域，并成为理论计算机科学领域的先驱，编写了两本教科书和许多研究论文。McNaughton曾与王浩一起学习研究自动机，证明了有限状态机与正则语言等价的McNaughton定理等。他提出的McNaughton定理，McNaughton-Yamada定理，都是计算机科学早期的重要结果，也是计算机复杂性研究的开拓性工作。
Robert F. McNaughton Jr., 90, passed away peacefully on Thursday, June 5, 2014 at Samaritan Hospital, after a brief illness. Robert was born and raised in Brooklyn, son of the late Robert and Helen McNaughton. After honorably serving his country in the United Sates Army during World War II, he graduated from Columbia University and received his Ph.D. in philosophy from Harvard. He transitioned to the field of computer science in the 1950's and became a pioneer in the field of theoretical computer science, authoring two textbooks and many research papers. He served as a professor at Rensselaer Polytechnic Institute until his retirement. In the course of his career he educated many students who became successful in the field. Robert believed strongly in civil liberties and human rights and gave both time and money towards improving them in the world. He and his wife made contributions to many charities, among which was the Friends of Chamber Music which he served as treasurer for many years. He was predeceased by his beloved wife, Vivien Leonard McNaughton; and his grandson, Brian Deppa. He is survived by his children, Nick McNaughton and Sarah (Timothy) Deppa; grandchildren, Jeffrey and Lisa Deppa; brother-in-law, Dr. Edward (Clee) Leonard; and nephews, Eric and Douglas Leonard, and their families. He will be remembered for his warmth, kindness and sense of humor. He was a wonderful son, husband, father, grandfather, colleague, teacher and friend. Services will be held on Monday, June 9, 2014 at 11 a.m. at the Chapel + Cultural Center, 2125 Burdett Ave., Troy. Interment to follow in St. Mary's Cemetery, Waterford. Viewing hours will precede the service at the chapel from 9:30 until 11 a.m. In lieu of flowers, contributions may be made to Friends of Chamber Music and Amnesty International in memory of Robert F. McNaughton.
Obituary
Robert McNaughton
1924 – 2014
The scientific community receives with sadness the news of the death of Robert McNaughton, a pioneer of theoretical computer science who has shaped our field by his ingenious contributions reported in a large number of lucid and highly influential papers.
Bob McNaughton grew up in Brooklyn in New York City. His undergraduate degree is from Columbia University and his doctorate from Harvard, where his advisor was Willard Van Orman Quine. Several of his fellow Quine students became distinguished logicians: William Craig, Henry Hiz, Hughes Leblanc, John Myhill, and Hao Wang. Starting from his dissertation On Establishing the Consistency of Systems (1951), McNaughton’s early work - often in collaboration with Wang was devoted to set theory and problems of relative consistency. At the same time he made fundamental contributions to philosophy of mathematics (in Philosophical Review) and to the metamathematics of number theory (in Transactions of the American Mathematical Society).
In the late 1950’s and early 1960’s, at the Moore School of Electrical Engineering of the University of Pennsylvania, he turned to the theory of finite automata and regular languages. An influential paper with his Penn PhD student Hisao Yamada supplied a lucid treatment of finite automata in relation to regular expressions. In the 1960’s, he moved to Rensselaer Polytechnic Institute, where he stayed until his retirement.
In the sequel McNaughton was one of the key researchers founding a classification theory of regular languages. This is documented by the monograph (with S. Papert) Counter-Free Automata, in which he tied the class of star-free languages to first-order logic, supplying also several other characterizations, e.g., in terms of permutation-free automata and reset-free nerve nets, and taking up also Schützenberger’s Theorem on the equivalence between star-freee xpressions and group-free monoids. Further topics of this research were the notions of ”loop complexity” of finite automata and their relation to star-height, and a characterization (with Kim and McCloskey) of the class of locally testable languages.
By the mid-sixties McNaughton had become an established name in four fields: hilosophy, mathematical logic, formal linguistics, and computer science.
For many researchers, McNaughton is best known for his work on automata over infinite strings. In his landmark paper of 1966, Testing and Generating Infinite Sequences by a Finite Automaton, he demonstrated the central theorem of omega-automata theory, namely the determinization of nondeterministic Büchi automata by a transformation into deterministic Muller automata. Often this result is referred to as ”McNaughton’s Theorem”. His ingenious construction motivated research that is pursued until today, aiming at reducing the number of states of deterministic automata and at unifying determinization with other constructions (such as complementation).
At the same time he addressed ”Church’s synthesis problem”, which asks for a construction of a non-terminating finite-state transducer, given a specification of the desired relation between input stream and output stream. It was McNaughton who proposed to study this problem in the framework of infinite games, thus starting a development which has led to a fruitful and active branch of current theoretical computer science. McNaughton’s proposal was first presented in a 1965 MIT technical report Finite-State Infinite Games. Also his later paper (of 1993) Infinite Games Played on Finite Graphs and his last contribution in this area, titled Playing Infinite Games in Finite Time (2000), were influential in developing this theory and motivating new approaches to solve infinite games.
Another important area of McNaughton’s research, into which he entered in the early 1980’s, was string rewriting systems (or Thue systems). One of the outcomes of this research, done together with his doctoral student P. Narendran and with F. Otto, was the concept of ”Church-Rosser Languages” or ”McNaughton Languages”, leading to the JACM (1988) paper Church-Rosser Thue Systemsand Formal Languages. He also made contributions to the study of special string rewriting systems (where one side of the identities is the empty word) and to the termination problem for single-rule string rewriting systems.
Bob McNaughton was a great teacher. His PhD students include John Corcoran, Anthony Dos Reis, David Hannay, Robert McCloskey, Paliath Narendran, Gil Porter, John Spagnuolo, Robert Winder, and Hisao Yamada. For many other former students, among them Aravind Joshi and Samuel Litwin, he was an inspiring mentor and role model. His textbook Elementary Computability, Formal Languages, and Automata (1982) is a masterpiece in clarity, supplied with many brilliant exercises.
All those who knew Bob McNaughton will keep precious memories of him as a warm-hearted and generous person. The community of theoretical computer science will miss his pioneering leadership and masterful creativity.
John Corcoran, Paliath Narendran, Wolfgang Thomas
延伸阅读
《麻省理工技术评论》、《君子》、《财富》杂志评定的2016年最佳书籍之一
入选“2017年度最激动人心之科学著作”的决选名单
《机器崛起》已在德先生旗下求知书店上架（识别下方二维码可进入购书直通车），现预定本书享8折优惠！
求知书店
《机器崛起（Rise of the Machines）》英文原版一经发售便被众多媒体广泛报道，并得到了高度评价，以下为相关媒体名单：《书单》、《电脑科技杂志》、《宇宙杂志》、《君子》、《金融时报》、《法兰克福汇报》、《法兰克福汇报大学报》、《星期五》、《卫报／观察家报》、《国际事务》、《柯克斯书评》、《自然》、《新苏黎世报》、《新科学家》、《纽约时报》、《展望杂志》、《科学美国人》、《旁观者》、《科学光谱》、《保准报》、《南德意志报》、《日报》、《技术评论》（德国）、《宇宙》、《华尔街日报》、“战争困境”网站；澳洲广播电台（澳大利亚）、巴伐利亚电台、德国广播电台、德国国家电台文化台、美国国家公共电台市场频道、西德广播电台、德国三星电视台。
德先生精彩文章回顾
在公众号会话位置回复以下关键词，查看德先生往期文章！
人工智能｜类脑研究｜人机大战｜机器人
虚拟现实｜无人驾驶｜智能制造｜无人机
科研创新｜网络安全｜数据时代｜区块链
……
更多精彩文章正在赶来，敬请期待！
点击“阅读原文”，移步求知书店，可查阅选购德先生推荐书籍。