1. 研究目的与意义（文献综述）

细胞自动机（cellular automata,简称CA）由John.Von.Neumam和Stanislaw M. Ulam于20世纪40年代末提出。他介绍了细胞自动机为一种可能机器自我复制的模型。自那以后，细胞自动机作为一种大规模的并行计算模型获得普及。在70年代，数学家JohnConway提出了生命游戏（lifeof game）的一种特殊的细胞自动机。在80年代，Stephen Wolfram对细胞自动机的状态空间和半径进行简化，获得了具有组成单元结构的规则简单性、单元之间作用的局部性和信息处理的高度并行性等优点的细胞自动机。Wolfram对细胞自动机按照动力学行为进行了分类，由此引发了国际学术界研究细胞自动机的热潮。进入90年代，细胞自动机的发展进入了百花齐放的局面。以美国Santa Fe学派为代表的研究专家基于对细胞自动机的深入研究，提出和发展了人工生命。同时，人工生命的发展又为细胞自动机赋予了新的含义，细胞自动机模型得到了科学界的重新认识和认可，并在次成为了科学研究的前沿课题，其理论和方法得到了进一步的提高。

细胞自动机的简单规则能够产生没有统计规律的复杂性表现，以其并行性的特点，被广泛应用于生活中的各个领域：经济、交通、地理、复杂系统研究、生物模拟、计算机技术等等。在社会学中，细胞自动机可以用于研究经济危机的形成与爆发过程，以及个人行为的社会性，或者传播现象，如服装流行色的形成舆论的传播的社会现象。在生物学中，由于细胞自动机的设计思想来源于生物学自繁殖现象，它在生物学上的应用更为自然而广泛。例如细胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索、艾滋病病毒HIV的感染过程、自组织和自繁殖等生命现象的研究，以及克隆技术的研究等。在信息学中，细胞自动机用于研究信息的保存、传播、扩散的过程。另外，2维细胞自动机也大量应用于图像处理和模式识别中。在计算机科学研究中，细胞自动机可以用来构建并行乘法器、素数过滤器、并行处理器、排序器和容错计算器等。细胞自动机具有自我复制能力，具有强大的计算功能，可以解决一些NP完全问题。

可逆性是细胞自动机的一个重要特性，已经被国内外的学者进行了深入的研究，其中一维细胞自动机的可逆性问题已经得到了很好的解决，而二维及更高维次的细胞自动机的可逆性问题被Kari J等人指出是不可判定的。但当高维细胞自动机的规则被限制为线性的时候，其可逆性问题还是可以被部分解决的。

2. 研究的基本内容与方案

本研究主要集中在二维线性细胞自动机的可逆性问题上，并把问题抽象为细胞自动机的转移矩阵的奇异性问题。由于二维细胞自动机的转移矩阵相较于一维的更为复杂，本研究准备综合考虑一维细胞自动机可逆性的研究方法，及相关学者有关于二维细胞自动机可逆性的研究方法，选取其中合适的一种，进行更加深入的研究。

为了有助于研究，本研究准备使用wolfram和matlab语言进行细胞自动机的行为演示和可逆性结果的预测与验证。其中wolfram语言的创始人stephen wolfram是细胞自动机的重要研究者，所以其语言带有有关细胞自动机的相关函数，因此我将用这门语言来生成细胞自动机的演示数据，而matlab主要进行可逆性结果的计算及图像与视频的生成。

由于在本次研究中，相关参数的可能性众多，所以本次研究不准备寻找问题的统一解，而是重点关注于某些特殊的情况，寻找部分参数条件下的可逆性结论。同时，对于以寻找到的可逆性结论，我将在论文中给出证明，对于未证明的所发现的相关可能规律，我也将写在论文中。

3. 研究计划与安排

第1-3周：查阅相关文献，撰写开题报告

第4-6周：完成相关程序的编写，同时阅读相关文献

第7-10周：进行相关研究

4. 参考文献（12篇以上）

[1]wolfram s. a new kind of science[m]. wolfram media, 2002

[2] kari j. reversibility of2d cellular automata is undecidable[j]. physica d nonlinear phenomena, 1990,45(1):379-385.

[3] kari j. reversibility andsurjectivity problems of cellular automata[j]. journal of computer amp; systemsciences, 1994, 48(1):149-182.