- 上一篇：学术信息平台国内外研究现状综述
- 下一篇：无线通信国内外研究现状和发展趋势
20世纪50年代，Von Neumann提出了元胞自动机的概念，它最初用于模拟生命系统所持有的自我复制现象，是描述自然界复杂现象的简化模型。从此，用元胞自动机来构造具有生命特征的机器成为科学界的一个新的方向，而对元胞自动机理论本身的研究开始逐步展开。70年代，英国数学家John Conway编制出了著名的“生命游戏”。它仅有简单的几条规则组合，但是却能产生无法预测的延伸、变形和停止等复杂工作，并最终被证明与图灵机等价。时至今日，该模型仍然是认识和探索复杂性的典型范例。八九十年代，元胞自动机不断的被简化与改进，其理论和方法得到的进一步的提高。进入21世纪之后，随着计算机技术的发展，元胞自动机更是作为一个阐释自然的新科学，被提升到了一个新的层次。63876
元胞自动机是一种时空离散的局部动力学模型，是复杂系统研究的一个典型方法，在空间复杂系统的时空动态模拟研究中非常适用。它不同于一般的动力学模型，因为元胞自动机并不是由严格定义的物理方程或函数确定的，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称。在这一模型中，散布在规则格网中的每一元胞都取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化，时间、空间、状态都离散是其最显著的特点。每个变量只能取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。
元胞自动机的应用非常广泛，包括社会、经济、军事和科学研究的各个领域。应用领域涉及生态学、信息学、计算机科学、数学、物理学等。在生态学中，基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点；在信息学中，元胞自动机用于研究信息的保存、传递、扩散的过程；在计算机科学中，元胞自动机可以被看作是并行计算机而用于并行计算的研究。另外，元胞自动机还应用于计算机图形学的研究中；在数学中，元胞自动机可用来研究数论和并行计算；物理学中，除了格子气元胞自动机在流体力学上的成功应用，元胞自动机还应用于磁场、电场等场的模拟，以及热扩散、热传导和机械波的模拟。另外，元胞自动机还用来模拟雪花等枝晶的形成。论文网
然而将元胞自动机应用在伪随机数的生成上，还要追溯回上世纪八十年代。八十年代中期，Wolfram首先简化了原始的元胞自动机，这对当时的元胞自动机理论及应用产生了极大的推动作用。1985年，他又提出了一种基于一维元胞自动机的伪随机数生成方法。同时他还指出，造成元胞自动机能产生伪随机数的原因是元胞自动机本身的非线性计算复杂度。Wolfram的成果证明，由最大长度元胞自动机生成的序列，其随机性明显优于其他广泛使用的方法，例如线性反馈位移寄存器，同时随着超大规模集成电路技术的显著进步，局部邻域元胞自动机的简单结构的实现成本将会越来越低。
一维元胞自动机伪随机数生成器具有非常简单的结构，虽然运算速度快，但是早期的部分生成器产生的随机序列的随机性相对较差。为了提高随机性，人们又把目光投向了二维元胞自动机伪随机数生成器。由于二维元胞自动机是多个一维元胞自动机的组合，其结构也就变得更加复杂，因此，二维元胞自动机伪随机数生成器获得了比一维更好的随机性。但是也正是因为结构复杂，相对地，它失去了一维元胞自动机伪随机数生成器的计算高效性。