什么是无限自动机论?

[拼音]：wuxian zidongjilun

[外文]：infinite automata theory

研究存储量无限的离散数字系统功能和结构以及两者关系的的理论，是自动机论的次级学科。数字电路这类物理系统，只包含有限个记忆元件，它的存储量是有限的。但是，稍复杂的算法，例如整数乘法所要求的存储量往往是无限的。离散数字系统按照存储量分为两大类：存储量有限的和存储量无限的。后者的数学模型为各种无限自动机。在无限自动机论中，主要研究信息加工系统和计算过程的数学模型、模拟、计算、识别和限制等问题。

从计算机的逻辑结构出发，抽象出它的数学模型，将一个自动机看作一个由控制器和它的外部环境组成的系统。控制器为一个有限自动机（见有限自动机论）。外部环境由一种数据结构刻划。控制器从外部环境提取信息(输入)，根据这些信息和控制器所处的内部状态，产生改变外部环境的指令(输出)并改变控制器的内部状态。自动机一步一步地重复这种过程，对外部环境中的数据进行处理。按照外部环境及其与控制器的相互作用方式的不同，提出许多种不同的自动机。例如，一个单带单头图灵机，它的外部环境可看作是一条可向一边或两边延伸的、分成格子的带子，带子上存储的数据可用字的有序对(xl，xr)表示，控制器可感知xr的左端字母，发出指令改写这个字母，将xl的右端字母连接到xr的左端(左移一格)，或将xr的左端字母连接到xl的右端(右移一格)。一个单寄存器机器的外部环境可看作是一个位数不受限制的寄存器，它存储一个字x，控制器可感知x的左端字母，发出指令去掉x的左端字母，或在x的右端连接一个字母。自动机的外部环境可起存储量无限的存储器的作用，现实的计算机的存储量是有限的，因此自动机是计算机的一种理想的数学模型。

另一种刻划方法把一个自动机看作一个程序。例如作为图灵机的一种变型提出来的 B机器。它是一个程序，指令系统由条件转移、在注视格子上写上记号*、 左移一格和右移一格所组成。一个无限制寄存器机器也是一个程序，指令系统包括：去掉第i寄存器中左端字母，在第i寄存器的右端连接一个字母，将第i寄存器清除为空字，传送第i寄存器的内容到第j寄存器，无条件转移，按照第i寄存器中左端字母转移。

模拟指通过简单的编码在一个自动机上实现另一个自动机的功能。图灵机和许多其他自动机都可以互相模拟。

在自动机的程序方向中，特别注意研究指令系统对计算能力的影响。例如 B机器或以擦指令代替写指令的机器，双计数器机器（指令系统为左移一格、右移一格和条件转移），寄存器机器，它们的计算能力和图灵机相同。但是，当条件转移指令换为重复指令时，所计算的函数减少为原始递归函数（见可计算性理论）。

一个自动机的通用性指它能模拟任何自动机。A.M.图灵构造出第一个通用自动机。C.E.仙农用机器状态数与带子字母数的乘积作为通用图灵机简单性的一种衡量标准。在60年代初已构造出一个7状态4字母单带通用图灵机；在二维带图灵机的范围内，还可改进到2状态2字母。

图灵机等一般自动机所识别的集恰是递归可枚举集，推广到非确定自动机的情形（即控制器是非确定有限自动机）不增加识别能力。识别能力介于有限自动机和一般自动机之间的机器，被认为更接近现实计算机而受到广泛研究。已提出多种不同的自动机。对每种自动机，按照确定和非确定、数据结构的类型、机器与环境间相互作用的方式以及时间空间限制，可再分为许多类。每一类自动机所识别的集构成一类语言。主要研究的问题是各种限制类型的自动机识别集的刻划、包含关系和代数性质。与形式语言有关的一个结果是，在乔姆斯基分层下的四类形式语言对应四类自动机的识别集：0型语言对应图灵机可识别，1型语言对应非确定线性有界自动机可识别，2型语言对应非确定下推自动机可识别，3型语言对应有限自动机可识别。

从实现的角度研究在计算时间、存储空间或其他资源受到限制的情况下自动机的计算和识别能力。从有限自动机所计算的函数类F0出发， 以 Fi中函数作为图灵机计算的空间界限得出函数类Fi+1，则F0，F1，F2，…构成卡尔玛初等函数(由四则运算与连加、连乘定义出的自然数上的函数)的一个分层，即Fi是Fi+1的真子集， 且所有Fi的和集为初等函数类。用阿克曼函数或增长速度类似的函数作为图灵机等自动机的时间或空间界限，所得的函数类构成原始递归函数的一个分层；这些函数类与按照原始递归式（或联立原始递归式）的嵌套重数分层的函数类一致。这些结果属于亚递归分层问题。另一个问题为研究各类自动机在资源限制下所计算的函数类或识别集的类的包含关系。例如，k带图灵机的实时识别能力比 k-1带图灵机强；每条带上具有多个读写头的图灵机可由每条带上只有一个读写头的图灵机实时地模拟。

任一个可计算函数或可识别集，在计算时间和存储空间受限制的情况下是否可计算或可识别的问题，从肯定方面涉及到好的算法的设计问题，从否定方面涉及到问题固有复杂性的下界估计问题。以回文识别为例，回文可由多带图灵机实时识别。将计算模型限制于单带图灵机的范围，回文识别的固有时间复杂性（最坏情形）为平方级。这就是说，任何识别回文的单带图灵机T都存在常数C，使得几乎所有回文为x，T 识别x所需的时间tT(x)不小于x的字长│x│的平方的C倍，即tT(x)≥C′|x|2；且这一下界不能再改进，因为存在识别回文的单带图灵机T′和常数C′，几乎对所有字x都有


。对加法和反字的计算时间，也有类似回文的结果。

无限自动机的理论有助于理解计算过程的本质方面，在程序设计语言和编译方面都有具体的应用。面向现实计算进行研究仍然是发展的趋势。代数方法将受到更多的注意和发展。

参考书目

M.L.Minsky，Computation-Finite and Infinite Machines，Prentice Hall， Englewood Cliffs，New Jersey，1967.