01 · 计算人生
成果背后的人
达纳·斯科特是一位把数理逻辑与程序设计基础联系起来的逻辑学家。他与迈克尔·拉宾提出非确定有限自动机，并证明它与确定自动机之间的关系。后来，他与克里斯托弗·斯特雷奇发展指称语义，为程序赋予数学意义。1976 年共同获得图灵奖、表彰自动机研究时，他任职于牛津大学。
理解这项贡献
迈克尔·拉宾和达纳·斯科特研究有限自动机：用有限个状态描述行为的机器。非确定性允许下一步有多种选择，只要某条合法路径到达接受状态，字符串就被接受。对于有限自动机，这个看似更强的模型可以转换为确定性模型。
为什么重要
自动机理论支撑着模式识别工具、语言分析和对计算模型的研究。