01 · 计算人生
成果背后的人
迈克尔·拉宾帮助奠定自动机与算法的数学基础。他与达纳·斯科特的研究表明，非确定有限自动机可以识别与确定自动机相同的语言。他后来开创随机算法研究，并对密码学作出重要贡献。他长期任职于耶路撒冷希伯来大学，承担学术领导工作并曾任校务长，后来还在哈佛担任教授。
理解这项贡献
迈克尔·拉宾和达纳·斯科特研究有限自动机：用有限个状态描述行为的机器。非确定性允许下一步有多种选择，只要某条合法路径到达接受状态，字符串就被接受。对于有限自动机，这个看似更强的模型可以转换为确定性模型。
为什么重要
自动机理论支撑着模式识别工具、语言分析和对计算模型的研究。