什么是自动机理论?

[拼音]：zidongji lilun

[外文]：automata theory

研究自动机的分析与综合问题的数学理论，是控制论的一个重要分支。在自动机理论中，自动机都是指抽象自动机，即能变换和处理信息的离散系统的动态数学模型。因为自动机理论早期的研究工作与数理逻辑有关，所以数学家把它看作是数学的一个分支。因为自动机可作为计算机和计算过程的数学模型，所以计算机专家把它看作是理论计算机科学的一个分支。自动机理论由抽象理论、结构理论和自组织理论三个部分组成。

1936年英国数学家A.M.图灵提出一种抽象自动机，称为图灵机，用来定义可计算函数类，开创了自动机的抽象理论。1935～1938年苏联数学家В．И．舍斯塔科夫和美国应用数学家C.E.香农分别独立地应用布尔代数来分析和综合继电器接点电路，建立开关网络理论，又称逻辑自动机理论，开创了自动机的结构理论。1943年美国神经生理学家W.S.麦卡洛克和数学家W.皮茨在《关于神经活动中思维的逻辑演算》一文中，提出自动机的自组织理论。1945年美国数学家 J.von诺伊曼设计出存储程序式通用电子数字计算机EDVAC,并研制成功，世称诺伊曼机。诺伊曼机成为现代通用电子数字计算机的主要模式,1948年J.von诺伊曼对各种人造自动机和天然自动机进行比较，提出建立自动机的一般理论来概括它们的共同规律，并提出自繁殖和自修复等自组织理论。1948年美国数学家N.维纳在《控制论》一书中对现代自动机作了详细的分析，指出自动机的功能是变换和处理信息，灵敏自动机的理论是一个统计的理论。这就为自动机理论奠定了基础。1956年C.E.香农和J.麦卡锡合编的著名论文集《自动机研究》一书出版。

50～60年代自动机理论得到迅速的发展。先后提出有限自动机(S.C.克林,1951；E.F.穆尔,1956)、无限自动机(M.明斯基,1967)、概率自动机(C.E.香农,1956;T.L.布思,1965)、模糊自动机(E.S.桑托斯,1968；傅京孙，田中，1969)、细胞自动机（E.F.古德,1968）等多种抽象自动机；建立了形式语言与自动机的对应关系（N.乔姆斯基,1959,1964）；创立了自动机的综合理论（B.M.格罗什科夫，1961）、半群理论（K.克劳恩和J.L.罗兹，1965）和可靠性理论（J.von诺伊曼,1952）。70年代后，由于大规模集成电路和并行计算机发展的需要，细胞自动机得到了迅速的发展（A.林登迈耶，1976）。由于模式识别、人工智能和大系统理论发展的需要，模糊自动机越来越引起人们的注意。许多学者企图建立自动机的统一理论，因此自动机的代数理论也有较大的进展，开始研究范畴上的自动机。

在自动机的抽象理论中不考虑自动机本身的结构及其输入和输出信号的具体形式，把自动机作为一种数学系统，研究它的一般数学性质。抽象理论仅研究自动机在输入信号作用下发生的状态变化及此时产生的输出信号。自动机的抽象理论从数学上看就是一种可能性预先受到限制的算法理论，即机器算法理论，它是现代程序设计理论的基础。

1936年图灵提出用图灵机来定义可计算函数类开创了抽象理论的研究。60年代形成的自动机的半群理论,后来发展起来的自动机的代数理论，以及范畴上的自动机理论，是抽象理论的重要内容。50年代末提出的把自动机作为语言识别器，建立形式语言与自动机的对应关系，通过自动机得出相应文法的识别程序，从而实现面向文法的编译，产生编译程序的编译程序。把自动机作为计算过程的模型，可以用来研究算法、程序和计算复杂性理论。这些也都属于抽象理论的范畴。抽象理论的主要发展方向是建立自动机的统一理论。

自动机的结构理论是自动机抽象理论的进一步发展。结构理论研究的重点是自动机的综合、由元自动机构造自动机的方法以及对输入和输出通道传递的元信号进行编码的方法。

由于设计新型电子计算机的迫切需要，数字自动机的结构理论得到迅速的发展。通用电子数字计算机可以看作更广泛的数字自动机中的一类。数字自动机的结构理论涉及布尔代数、命题演算、谓词演算和信息论的有关问题。数字自动机的结构理论与数字自动机的综合问题直接有关，包括抽象综合、组合综合、结构综合、部件综合和可靠性综合。1938年C.E.香农就用布尔代数解决继电网络的组合综合，后来用于电子计算机逻辑网络的综合。40年代苏联学者В．И．舍斯塔科夫解决了数字自动机的结构综合和部件综合问题。到50年代S.C.克林和E.F.穆尔解决了抽象综合问题，后来D.D.奥芬卡姆夫和 F.霍恩又进一步发展了抽象综合。J.von诺伊曼解决了可靠性综合问题。到60年代苏联学者B.M.格罗什科夫把抽象综合和结构综合结合起来，使结构理论的表达形式适合于解决任何数字自动机的综合问题，建立了数字自动机综合的一般数学理论。

由元自动机构造自动机的方法主要有两类：

（1）级联方法，即用串联、并联和混联方法把若干台元自动机联成一台自动机，它具有树状、星状、网状等多种拓扑结构。级联方法的逆问题是级联分解问题，自动机的级联分解与大系统的分解等价。有限自动机的级联分解问题与有限自动机的半群结构有关，可以根据半群的结构理论和群的整除性理论解决。已经证明有限自动机级联分解定理。

（2）邻域连接方法，现已发展成为细胞自动机理论，在一致结构的大规模集成电路和并行计算机中得到广泛应用。

自动机的自组织理论是自动机的抽象理论和结构理论发展的结果。自组织理论涉及神经网络、人工智能、模式识别等许多方面，有时还要应用协同学、耗散结构理论和超循环理论等方面的成就。1943年W.S.麦卡洛克和W.皮茨关于神经网络的先驱性工作，对发展神经网络理论有深远的影响，促进了自组织理论的早期研究工作。1969年傅京孙、田中和E.S.桑托斯等人把模糊神经原的概念应用到自动机理论中来，使神经网络理论的研究工作得到新的发展，并使自动机理论开始用来研究复杂大系统的行为。

在自组织理论的研究中 J.von诺伊曼提出了一系列创造性的新概念。1948年他提出自繁殖机的概念。他所提出的关联的有限自动机的迭代阵列可用来研究字符的模式识别。1952年他提出著名的冗余技术，即用大量并行连接的可靠性低的自动机能构造出可靠性很高的自动机，后来发展成为容错自动机理论。在此基础上他又提出诺伊曼细胞空间的新概念，后来发展成为细胞自动机理论。

1958年F.罗森布拉特曾提出认知机的网络结构，模拟人的感受、认知和解题能力。50年代末到60年代初又在认知机的基础上提出自适应机和自学习机。1963年苏联学者В．И．瓦尔沙乌斯基等人又提出变结构自动机。1969年M.明斯基等人证明这类自组织机器的模式识别能力有限。到70年代便转向机器视觉的研究。

1968年E.F.古德提出的细胞自动机(即多元自动机)使自组织理论发展到一个新阶段。细胞自动机是在诺伊曼细胞空间的概念上发展起来的，它由大量相同的细胞按邻域连接方法关联组成，可以形成各种拓扑配置格局。在细胞自动机中一个细胞就是一台有限自动机，每一个细胞可以从相邻的细胞或外界环境取得输入信息，每一个细胞的输出信息可以传递给相邻的细胞或外界环境。因此，细胞自动机可以用来研究并行计算机的体系结构和大规模集成电路设计技术。有一种细胞自动机是二维无限棋盘格式的,每一方格代表一个细胞。它已被用来证明非平凡的自繁殖机的存在。如果每个细胞有三个状态和四个相邻细胞,并呈现园林格局（即除了时刻0以外在细胞空间中每一时刻细胞状态的模式均不会增加），他就可以用来计算任何可计算函数。另一种细胞自动机是采用棋盘形空间，一个外部输入可以传递到每一个细胞，一个细胞失去一个邻近细胞可用一个专用的边界信号代替。这种细胞自动机专门用作模式识别器。有一种图形细胞自动机只要求相邻细胞的数目是固定的，而不要求它们与一个细胞有固定的几何关系。这种细胞自动机比均匀关联的细胞自动机具有更强的功能。1976年荷兰生物学家林登迈耶提出动态细胞自动机，称为林登迈耶系统,即L系统。动态细胞自动机允许把细胞划分成子细胞而不管该细胞在细胞初始阵列中的位置。这种动态关联格式受到理论生物学家的注意，可用作生命体的生长和发育模型。有一种米利型细胞允许任何两个细胞之间进行瞬时通信。上述各种细胞自动机如采用米利型细胞还会有其他新的功能。

参考书目

C.E.申南、J.麦克卡赛编，陈中基编译：《自动机研究》，科学出版社，北京，1963。(C.E. Shannon and J.McCarthy(eds)， Automata Studies，Princeton University Press, Princeton, N.J.,1956.)M.A.Arbib，Theories of Abstract Automata，Printice-Hall, Englewood Cliffs, N.J.,1969.