| 词条 | 自动机论 |
| 释义 | zidongjilun 自动机论(卷名：电子学与计算机) automata theory 研究离散数字系统的功能和结构以及两者关系的数学理论。离散数字系统的时间坐标是离散的，表征系统的变量的值是数字量。数字电路、数字信道、自动电话交换机、数字计算机、程序和算法是数字系统的一些实例。在自动机论中，自动机是一个数学概念，作为离散系统的抽象模型。给定自动机的功能描述，综合出具有这种功能的自动机的结构；给定自动机的结构，分析它的功能，这就是自动机的综合和分析问题，它是自动机论的典型研究课题。 历史和发展 19世纪中期，英国G.布尔用数学方法研究思维规律的问题建立了逻辑代数，后人称之为布尔代数。1935～1938年，苏联В.И.肖斯塔科夫和美国C.E.仙农，独立地应用布尔代数于继电器接点电路的分析和综合，形成了开关网络理论。1936年，为了对能行性、机械过程或算法进行精确的数学描述，英国A.M.图灵提出一种理想计算机，后人称之为图灵机。1944年，W.S.麦克卡洛和W.匹茨用数理逻辑方法研究神经网络。40年代中期出现电子计算机以后，美籍匈牙利数学家J.诺伊曼在1948年提出建立自动机的一般逻辑理论，对各种人造自动机和天然自动机进行比较性研究，探索其共同规律。他还研究了自动机的自繁殖和自恢复问题。诺伊曼被认为是自动机论的创立者。 受计算机的影响，50年代初，开关网络的研究重点转移到一般的逻辑网络，特别是门电路类型开关网络。1954年前后形成了时序机（即有限自动机）这一重要数学概念。同时，从数字计算机的一种理想的数学模型的角度，开始对图灵机深入研究。1956年《自动机研究》论文集的出版，标志着自动机论已形成为一门独立的学科。 50年代以来，自动机论有了很大的发展。有限自动机的理论得到广泛深入和系统的研究，成为自动机论中最成熟的领域，并在许多工程上得到应用。无限自动机的理论主要是处理计算过程，对图灵机理论的研究一直在持续进行，对更自然的计算机数学模型的探索和在资源限制下自动机的功能的研究也有了较大的进展。概率自动机主要是概率有限自动机的理论，在1963年后有了较大发展。60年代后期以来，细胞自动机主要是在生物学和大规模集成电路技术的基础上成为自动机论中一个活跃的领域。同时，在抽象自动机方面，也开展了研究。 学科内容 自动机论可分为五个次级学科。 有限自动机论 包括开关网络理论，主要研究对象为继电器接点电路、数字电路、理想神经网络这类存储量有限的自动机。主要的研究问题是综合和分析问题。一种典型的问题提法是：研究由某种数学语言陈述的功能出发，设计出满足要求的有限自动机和实现它的逻辑网络的系统方法。这涉及到功能描述数学语言、状态化简、状态赋值、布尔函数化简、多值逻辑、组合复杂性和分解等问题的研究。另一个重要方向是1959年开始研究的可逆性问题，主要研究判别、求逆和结构问题。自动机作为转换器将输入序列变换为输出序列，没有输入的自动机可作为序列产生器，没有输出的自动机可作为序列识别器。有限自动机作为序列产生器是50年代中期开始深入研究的一个方向，代数方法得到了很好的应用。有限自动机作为序列识别器的研究方向，较早地建立了比较完善的理论。 无限自动机论 主要研究对象为算法和理想计算机这种存储量不受限制的自动机。研究的问题包括探索计算机和计算过程的数学模型，以及各种模型之间的关系。60年代初开始的一个重要研究问题是，在计算时间、存储空间和机器规模等资源受限制的情况下，自动机所计算的函数类和识别集的类的刻划、包含关系和代数性质。另一个从50年代末开始活跃的领域是，将自动机识别集作为形式语言的一种刻划方法，对各种限制类型自动机的功能的研究。 概率自动机论 主要研究对象是在环境或内部具有随机因素的(有限或无限)自动机。概率有限自动机（即随机时序机）是1948年仙农提出的，作为噪声信道的一种模型。60年代后开始系统地发展，主要是推广确定自动机的结果，研究实现、化简、识别和稳定性等问题。在自恢复自动机方面，50年代初诺依曼研究的由不可靠元件构造可靠系统的方向，到70年代发展为容错计算这一活跃的研究领域。另一个方向是对各种概率自动机所识别的语言的研究。 细胞自动机论 主要研究对象是由许多互相连接的小自动机并行运算形成的大自动机。这项研究始于诺依曼对自繁殖自动机的研究。从他提出的细胞空间概念发展出许多研究方向。与计算机有关的一个方向是具有细胞类型的并行计算机模型的研究，这些研究已应用到一些并行计算机的体系设计中。70年代活跃起来的另一个方向面向大规模集成电路技术，研究具有一致结构的各种细胞自动机的分析、综合和容错等问题。在发育生物学方面，1968年荷兰生物学家A.林顿梅伊尔推广了诺依曼的细胞空间概念，提出了一种动态细胞自动机的数学结构，通常称之为L系统，用以描述多细胞组织的发育过程。1974年以来，L-系统的理论是一个十分活跃的研究领域。 抽象自动机论 将自动机作为一种数学系统，研究它的一般数学性质。一个重要的研究方向为自动机的半群理论，它为有限自动机的分解问题提供了工具。另一个方向是研究范畴上自动机，目标是建立一个关于有限自动机、线性控制系统、树自动机、概率自动机和拓扑自动机等的统一理论。 与其他学科的关系和应用 自动机论是古老的数学学科的一个新兴分支。在它的形成和发展过程中，其他数学分支特别是数理逻辑起了很大的作用。自动机论和数理逻辑的一些领域交叉重叠，例如可计算性理论和无限自动机的功能理论都以算法为主要研究对象，但它们的侧重点不同。 自动机论与形式语言理论关系密切。一方面自动机作为形式语言的一种主要描述方法，另一方面形式文法也可作为自动机识别集的一种描述方法。自动机论与计算复杂性理论的一些领域交叉重叠，例如组合复杂性和计算复杂性。自动机论是计算机科学的基础理论中较早形成的部分。 自动机论又是控制论的一部分。自动机，包括有限自动机、图灵机和理想神经网络，是控制论系统的一种模型。自适应、自学习、自恢复和自繁殖自动机的研究，是典型的控制论问题。自动机论与控制论的其他部分关系也很密切。例如，自动机论与控制理论中的许多结果是类似的，这种类似性成为抽象自动机研究的一个出发点。 自动机论的形成受自动控制、计算机和数字通信技术的推动，它的成果又应用于这些技术学科中。自动机论探索和提供各种数字电路综合分析的系统方法。细胞自动机对并行计算机设计思想产生了明显的影响。自动机作为一种基本工具用于高级程序语言的编译设计。线性自动机作为伪随机序列产生器用途广泛。可逆自动机用于通信编码。 自动机论的形成和发展的部分原因，是对生物系统进行一般性刻划，例如在神经网络和自繁殖自动机方面的工作。基于多细胞组织的发育是执行一种“发育程序“的观念，自动机也用于研究生物发育。 参考书目 陶仁骥著：《有限自动机的可逆性》，科学出版社，北京，1979。 C.E.申南、J.麦克卡赛编，陈中基编译：《自动机研究》，科学出版社，北京，1963。(C.E.Shannon and J.McCarthy eds.，Automata Studies， Princeton Univ. Pr.， Princeton， N.J.，1956.) M.A.Arbib， Theories of Abstract Automata， Prentice-Hall，Englewood Cliffs， N.J.， 1969. |
| 随便看 |
百科全书收录78206条中英文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。