邬舒雯 熊明

1 引言

元胞自动机（Cellular Automata,CA）是一类时间和空间离散的数学系统，其特征是局部相互作用和内在的并行演化形式。元胞自动机这一概念起源于冯诺依曼（von Neumann）在“自动机的一般逻辑理论”（The General and Logical Theory of Automata）中所提出的二维自复制自动机系统。（参见[12]）元胞自动机结构、规则简单，但能产生复杂的行为模式，因此作为一类复杂系统的最简单数学表示，被广泛应用于交通运输、计算机科学、人工智能、生物科学、物理学等众多学科领域。

近年来，文[9]提出了能够将元胞自动机与自指语句相联系的观点。文中提出元胞自动机的演化过程与自指语句的修正过程这两个动态过程在本质上是相同的，这种相似性，使我们能够将元胞自动机和自指语句，一个属于计算机科学和一个属于逻辑学的两个不同研究领域的理论概念相互联系起来进行研究。文[9]主要研究了初等元胞自动机及其相关联的自指语句，从初等元胞自动机诱导出若干类悖论，并根据自指语句的特征对初等元胞自动机给出了一个分类。

文[9]用来分析自指语句的一个关键概念是修正序列，这是来自于修正理论（参见[5,6]）的基本概念。在这个理论中，自指语句分阶段按照修正规则与极限规则进行赋值，每个语句都可建立一个动态的赋值过程，这样的过程即为修正过程。本文基于文[9]提出的理论，将目光投向到更为复杂的二维元胞自动机系统中，研究一类特殊的冯诺依曼型元胞自动机及其相关的自指语句。……