01B

约 1018 个字 预计阅读时间 3 分钟

在上一节中，我们主要跟随的是 Conway 在 1960s 左右开始的路径，讨论了自动机作为一种代数构造的可能，并利用这种代数构造解决了一些问题。在这一节中，我们将跟随同时代的 S. Eilenberg 和 R. Kalman 等人的视角，尝试去讨论自动机的范畴视角，以及从系统论角度去讨论自动机，并在最后通过系统论中的对偶性揭示自动机构造中的对偶性，也就是上一节中提到的 Brzozowski 算法的深层原理。

S. Eilenberg 主要的研究方向在代数拓扑，与 S. MacLane 一起创立了范畴论。但是他对自动机理论贡献也非常卓越，主要的材料是 1967 年的论文 Automata in General Algebras 和 1974 年的专著 Automata, Languages and Machines。他提出的 X-Machine 我们在下一节中也会述及；R. E. Kalman 最著名的创造则是 Kalman 滤波器，他是控制系统的严格理论发展初期的重要领导者。在本节中涉及到的主要材料来自 1968 年的专著 Lectures on controllability and observability 和 1969 年的专著 Topics in Mathematical System Theory，后者的合作者之一 M. A. Arbib 则是我们这篇文章主要的发展来源之一，他和 E. G. Manes 在 1974 年到 1980 年的一系列论文彻底地将自动机范畴化这个论题带到学者的事业中来。另一份不可不提的文献来自于 H. Ehrig 和 M. Pfender，1972 年出版的 Kategorien und Automate。这本书虽然至今（在笔者所知范围内）没有英文译本，但确是比较早地提出自动机范畴化的概念的理论专著，事实上，我们也会大量引述这本专著中的一些内容，尤其是关于自动机和范畴极限的关联的部分。从本世纪初开始，更多这个方向的论文逐渐问世，主要讨论的是范畴化在自动机的简化方面的应用，虽然这个论题早已在 1972 年就被 J. Goguen 探讨过。本文最终部分关于 Brzozowski 算法的讨论，就大部分源于 F. Bonchi 等人在 2014 年的洞见。2008 年左右，A. Kurz 和 M. Gehrke 等人将 Conway 那种代数的对正则语言和正则语言恒等式、正则语言方程的讨论也纳入了范畴论的视域下。

讨论范畴论的中文书籍主要是李文威老师的《代数学方法》，在他的主页上可以获得电子版本，本文的记号和基本概念应当都与他的书一致。较新的英文书籍应当是 N. N. Jacobson 的 Basic Algebra 第二卷。很多引论则是作为代数几何的一个前置知识被书写的，例如 R. Vakil 著名的 The Rising Sea 中的第一章，以及哥伦比亚大学组织的 The Stacks project 的第四章；在数理逻辑中范畴学的应用也是非常重要的，我们在后面也会加以讨论，并利用这套语言统一不完备性定理、停机问题等等自指涉（self-referential）类型的问题。对于计算机专业的学生而言，Bartosz Milewski 的引论也是相当有益的，当然，并不足够。本系列中除一些特定问题外，所用到的范畴学不会超过 The Stacks project 中的内容，但李文威的书第一卷的内容及其他大部分这里列出的参考书都尚有一点不足。虽然笔者将对很多基本概念进行介绍，但因为篇幅及主题所限，不会给出很多很充分的例子，而范畴学本身又是极为抽象的数学领域，因此将这些参考文献列出，以备读者参考。如果需要更充分的资源，而且你也已经理解了足够多的基本概念，那么 nLab 也是很好的线上资源。