在计算机理论的重要学者中，不得不提克莱尼（Stephen Cole Kleene，1909—1994）。
克莱尼是一名美国数学家、逻辑学家，主要从事对可计算函数的研究，他的递归理论研究为奠定理论计算机科学的基础做出了贡献。
克莱尼于1934年在普林斯顿大学获得数学博士学位，论文题目是“形式逻辑中的正整数理论”，导师是阿隆佐·丘奇（Alonzo Church，1903—1995）。
丘奇在1936年的著名论文（基础数论中的不可解问题，An unsolvable problem of elementary number theory）中提出lambda演算，借助于克莱尼关于递归理论的工作来证明Hilbert提出的Entscheidungsproblem不可解。
摘自维机（https://en.wikipedia.org/wiki/Stephen_Cole_Kleene）：
[...] 递归函数理论在计算机科学中具有核心重要性。克莱恩在该领域做出了许多基础性成果，包括克莱恩范式定理（1936 年）、克莱恩递归定理（1938 年）、20 世纪 40 年代和 50 年代算术和超算术层次结构的发展、克莱恩-波斯特不可解度理论（1954 年）以及高阶递归理论。他于 20 世纪 50 年代末开始研究该理论，并于 20 世纪 70 年代末重返该领域。[...] 从 20 世纪 40 年代末开始，克莱恩还研究了第二个领域，即布劳威尔的直觉主义。他利用递归理论的工具，引入了递归可实现性，这是解释直觉主义陈述的重要技术。 1951年夏天，在兰德公司，他对第三个领域取得了重大突破，对有限自动机接受的事件给出了重要特征。[4]
[...] recursive function theory is of central importance in computer science. Kleene is responsible for many of the fundamental results in the area, including the Kleene normal form theorem (1936), the Kleene recursive theorem (1938), the development of the arithmetical and hyper-arithmetical hierarchies in the 1940s and 1950s, the Kleene-Post theory of degrees of unsolvability (1954), and higher-type recursion theory. which he began in the late 1950s and returned to in the late 1970s. [...] Beginning in the late 1940s, Kleene also worked in a second area, Brouwer's intuitionism. Using tools from recursion theory, he introduced recursive realizability, an important technique for interpreting intuitionistic statements. In the summer of 1951 at the Rand Corporation, he produced a major breakthrough in a third area when he gave an important characterization of events accepted by a finite automaton.[4]
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1462965.html?mobile=1
收藏
