什么是细胞自动机论?

什么是细胞自动机论?

[拼音]：xibao zidongjilun

[外文]：cellular automata theory

自动机论的次级学科，主要研究由小的计算机或部件，按邻域连接方式连接成较大的、并行工作的计算机或部件的理论模型。

J.诺伊曼在50年代初期研究自生长自动机的逻辑问题时，是以细胞空间作为主要工具的。根据他提出的细胞空间概念已发展出许多研究方向。并行计算机的体系设计和大规模集成电路技术，都应用这些概念来研究具有一致结构的各种细胞自动机的分析、综合和容错等问题。1968年A.林顿梅伊尔推广了诺伊曼的细胞空间概念，提出一种动态细胞自动机的数学结构──L系统，用以描述多细胞组织的发育过程。各种类型的细胞自动机都是由冯·诺依曼的细胞自动机推广而来的。诺依曼细胞自动机是最早的、最基本的自动机。

诺伊曼细胞空间

这种空间的形式像一个把行和列上的格子向上下左右无限扩展的无限棋盘。每一个格子都被看作是一个“细胞”，这些细胞都是相同的，具有29状态的确定的有限自动机，并假定都是在相同时刻改变自己的状态，即它们的动作在时间上是同步的。每个细胞和它的上下左右直接相邻的细胞构成它的一个邻域，它在时刻t+1的状态，由它的邻域中各个有限自动机在时刻 t的状态决定。有一个特殊的状态S0叫作静止状态。当细胞的邻域中的状态都是S0时，它的下一时刻的状态仍是S0，并且假定除了有限个细胞外，所有其余的细胞都处于这种状态。因而，尽管细胞空间是无限的，但在任何时刻人们只注意其中有限个。对细胞空间的每一个细胞赋予一个状态，并且保持其状态不是S0的细胞的个数为有限个，这种赋值叫作细胞空间的一个构形。在时刻t＝0的构形叫作初始构形。细胞空间以外的事物或信息只能在这个时刻对它起作用。在时刻t=0之后，构形的所有改变都按预先给定的规则自主地进行，即在t=0后不再有外来输入。初始构形完全决定以后各个时刻的构形，并且在每一（时间）步上只能改变一次。构形内的非静止状态细胞的集合叫作构形的支架。在前面所说的情况下，支架当然是有限集合。有限的细胞空间即称为细胞自动机。

诺伊曼细胞空间的所有细胞都在整数网格的结点上，细胞个数为无限。它满足下列条件：各个细胞都是确定的摩尔型有限自动机；采取五邻域一致连接模式（所有细胞有同样形状的邻域）；不带外部输入，不向外部输出；并且是静态的（邻域不随时间改变）。一般的细胞空间不必要这些条件限制，故此外还有非确定型细胞空间、米雷型细胞空间、连接模式非一致的细胞空间、带外部输入的细胞空间以及动态的细胞空间等。

棋盘格空间

细胞空间的一个直接推广。它有分配到各个细胞的统一的外部输入。或者说，棋盘格空间是一个程序控制的细胞空间。棋盘格空间里的每一个细胞能够被想象为有一个局部转移函数的有限集合。因此，棋盘格空间有一个全局转移函数的有限集合。程序中的各个“指令”选择在该时刻的转移中所使用的全局转移函数。

迭合空间

对细胞空间的一个细胞给定一个外部输入和外部输出，这个特定的细胞叫作“输入输出细胞”。这个细胞空间也就叫作迭合空间。

射击小分队问题与蜂王问题

细胞自动机理论中著名问题之一是射击小分队问题。在这个问题中，把各个细胞看作战士，其中一个当队长。开始时，除了作队长的细胞之外，所有其余细胞都处于静止状态，然后队长下令“开火”。问题是是否所有战士都能同时射击，即同时进入同一状态。射击小分队定理对这个问题给以肯定的答案。这个定理在非一致连接模式的情况下也成立。与此结果密切相关的另一结果是蜂王定理。它解决与射击小分队定理相反的问题，即要求设计一个细胞自动机使得所有状态开始时都处于同一个状态，最后有一个且只有一个细胞很快地被作为接受细胞──蜂王──标明出来。

图细胞自动机

仅要求邻域内细胞个数固定，而不要求这些细胞之间有任何固定的几何关系。这类细胞自动机比一致连接的细胞自动机更强有力。

动态细胞自动机

在这类细胞自动机中，不管细胞在初始细胞阵列中的位置如何，允许细胞分裂成为儿女细胞，并且允许细胞消亡。理论生物学家对这一类型自动机很感兴趣，把它当作为有生命物的发育模型。

语言识别器

细胞自动机不仅可以在形式上作为并行计算机的理论模型来研究，而且还可以作为语言（被机器接受的输入字的集合）识别器。一个语言被某种识别器所识别是指：识别器不仅接受该语言中的字，而且拒绝不属于该语言中的字。在维数高于1时，语言识别有时被看作模式识别。对于迭合自动机，如果每一(时间)步只输入一个字母，当字全部输完之后，如果输入输出细胞进入一个特别设计的接受状态，就认为它接受了这个字。语言的所有的字都被接受时就称为迭合自动机语言。类似地，棋盘格自动机和一维细胞自动机也可以用作语言接受器。

用细胞自动机的并行计算方式可实现一些并行计算机和识别器的设计。细胞自动机对于集成电路的设计方法具有重要意义。大规模集成电路采用细胞阵列形式具有明显的优点。生物学推动了有关自动机的理论研究。反过来，有关自动机理论的发展为生物发育学提供了一种数学模型和方法。细胞自动机论的研究与形式语言的研究更是息息相关，各种细胞自动机的识别能力，以及它们所能识别的各种语言类与各类形式语言之间的关系都还处于探讨中。另外，各种类型细胞自动机的性质，以及它们彼此之间的关系也都是人们关心的课题。

参考书目

A.W.Burks ed.， Essays on Cellular Automata，University of Illinois Press， Urbana， Illinois， 1970.F.C.Hennie Ⅲ， Iterative Arrays of Logical Circuits，M.I.T.Press and John Wiley Sons， New York，1961.