【Linux·基础篇】Shell 基础|正则表达式:从神经元模型到多流派并存(二)

前情提要：在往期文章《【Linux·基础篇】Shell 基础｜正则表达式：从神经元模型到多流派并存（一）》的结尾，我们留下了一个悬而未决的问题：由逻辑单元组成的神经网络，能力边界在哪里？1943 年之后的近十年里，这个问题无人能答。直到一位年轻数学家注意到麦卡洛克和皮茨的工作，并决定用他熟悉的语言——数学——给出回答。他的答案如此简洁，以至于七十多年后的今天，我们仍然在使用它。

一、1951–1956：数学家的洞察——克莱尼的正则事件

麦卡洛克和皮茨的论文引起了一位美国数学家的注意，他叫斯蒂芬·科尔·克莱尼（Stephen Cole Kleene）。

克莱尼的学术背景使他恰好站在了回答这个问题的有利位置。他的博士导师是阿隆佐·邱奇（Alonzo Church）——lambda 演算（lambda calculus）的发明者和可计算性理论的奠基人之一。可计算性理论（computability theory），早期称为递归理论（recursion theory），研究的是“什么能被计算”这一根本问题。克莱尼本人也是这一领域的创始人之一，与艾伦·麦席森·图灵（Alan Mathison Turing）等人并列为理论计算机科学的先驱¹。正是出于对计算本质的深刻理解，克莱尼才对神经网络模型产生了浓厚的兴趣。

他想知道一个根本性的问题：由这种简单的逻辑单元组成的网络，到底能识别什么样的模式？换句话说，这些网络的能力边界在哪里？

为了回答这个问题，克莱尼在 1951 年为兰德公司（RAND Corporation）撰写的备忘录中，发明了一套简洁的代数符号²。这套符号只有三种基本运算：

• • 连接：一个东西紧接着另一个东西。
• • 并（∨，即逻辑上的“或”关系）：要么匹配这个，要么匹配那个。
• • 克莱尼星号（*）：前面的东西可以出现零次或任意多次。

克莱尼把用这套符号描述的模式集合称为“正则事件”（regular events）。他在 1956 年发表于《自动机研究》（Automata Studies）论文集中的文章进一步证明了，这套看似简单的符号，恰好能够精确描述麦卡洛克-皮茨神经网络所能识别的全部模式。这个结论——后来被称为克莱尼定理——在数学上建立了“正则事件”与“有限自动机”（一种只有有限内存的抽象机器）之间的等价关系³。

今天我们所说的“正则表达式”（regular expressions），指的正是描述这些正则事件的符号表达式。克莱尼在论文中使用的原始名称是“正则事件”，后来这套符号被应用于文本编辑器和编程工具中，“表达式”这一名称因其直观而逐渐取代了“事件”。

这个发现最初纯粹是数理逻辑和自动机理论的成果，没有任何实际应用。值得一提的是，正则表达式只是克莱尼众多贡献中的一个——他同时是递归理论的奠基人之一。他对神经网络的研究，很大程度上是出于对“计算”这一概念本身的数学本质的探索。他大概从未想过，这套符号会在几十年后成为每个程序员工具箱中的利器。

【注 1】克莱尼、图灵与同一位导师有着深厚的学术渊源——阿隆佐·邱奇。三人都是可计算性理论的创始人。他们的工作共同奠定了理论计算机科学的基础。

阿隆佐·邱奇（Alonzo Church，1903–1995）是美国数学家、逻辑学家，lambda 演算的发明者，可计算性理论的创始人之一。他于普林斯顿大学任教近四十年，指导了 31 名博士生，其中包括克莱尼（1934 年毕业）和图灵（1938 年毕业）。1936 年，邱奇独立证明了判定性问题的不可解性，提出了“邱奇论题”（Church's thesis）；同年，邱奇创办了《符号逻辑杂志》（Journal of Symbolic Logic），并担任其评论栏目编辑长达 43 年（1936-1979）。

斯蒂芬·科尔·克莱尼（Stephen Cole Kleene，1909–1994）于 1934 年在邱奇指导下获得博士学位，后任教于威斯康星大学麦迪逊分校（University of Wisconsin–Madison）。他在递归函数理论方面做出了基础性贡献，是可计算性理论的创始人之一，也是正则表达式的发明者（1951 年）。

艾伦·麦席森·图灵（Alan Mathison Turing，1912–1954）是英国数学家，图灵机的发明者。1936 年，图灵独立证明了停机问题的不可解性，提出了“图灵论题”（Turing's thesis）；同年，图灵在听闻邱奇的成果后，于当年晚些时候前往普林斯顿，在邱奇门下攻读博士学位（1938 年毕业），与邱奇一道为可计算性理论奠定了基础。

“邱奇论题”和“图灵论题”本质上说的是同一件事——lambda 演算和图灵机在计算能力上是完全等价的，即一个函数能用 lambda 演算表示，当且仅当它能用图灵机计算。

1952 年，克莱尼在其著作《元数学导论》（Introduction to Metamathematics）中首次将邱奇和图灵的理论分别称为“邱奇论题”“图灵论题”，并将两者合并称为“邱奇-图灵论题”（Church–Turing thesis）——该论题认为，任何直观上可计算的函数都可以用图灵机或 lambda 演算来描述，为整个计算机科学奠定了哲学基础。

【注 2】Kleene, S.C., Representation of Events in Nerve Nets and Finite Automata, RAND Corporation Memorandum RM-704, 1951. 正式发表为：Kleene, S.C., "Representation of Events in Nerve Nets and Finite Automata", in Automata Studies, Princeton University Press, 1956, pp. 3-41.

【注 3】有限自动机：可以想象成一台非常简单的机器，它有一组有限的状态（比如“开着”和“关着”），每读入一个字符，就根据规则从当前状态跳转到另一个状态。如果读完全部字符后停在“接受状态”，就说明匹配成功。我们在日常生活中也能找到有限自动机的影子：地铁闸机就是一个简单的例子——它有两种状态（“锁定”和“解锁”），投币让它解锁，推杆通过后它又锁上。

二、结语：纸面上的等待

克莱尼用三种运算定义了“正则事件”，精确刻画了神经网络的计算能力。但这套符号在诞生之初纯粹是纸面上的数学，没有任何实际应用。它还需要等待一个让它“活过来”的契机。这个契机，来自十几年后的一款文本编辑器。

此番炼器手札，炉火尚未全熄。若道友观之有趣，或可暂留此间，结一尘缘。待下回开炉铸器，新得感悟，必先与同道分享。