细胞自动机论的简单小结

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

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

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

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

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