元胞自动机.doc

(CellularAutomata,简称CA,也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网(LatticeGrid)中的每一元胞(Cell)取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。(Automaton)通常指不需要人们逐步进行操作指导的设备(夏培肃,1984)。例如,全自动洗衣机可按照预先安排好的操作步骤作自动地运行;现代计机器算机能自动地响应人工编制的各种编码指令。完成各种复杂的分析与计算;人则将自动控制系统和人工智能结合,实现类人的一系列活动。另一方面,自动机也可被看作为一种离散数字动态系统的数学模型。例如,(TuringAM.,1936)。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器,并可执行如下操作:?读写头在存储带上向左移动一格;?读写头在存储带上向右移动一格;?在存储的某一格内写下或清除一符号;?条件转移。图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。实际上,一切"可计算"函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。根据存储带是否有限,可将自动机划分为有限带自动机(FiniteAutomaton)和无限带自动机(InfiniteAutomaton)。由于图灵机有无限长的存储带,所以为一种无限带自动机。有限带自动机常用作数字电路的数学模型,也用来描述神经系统和算法;而无限带自动机主要用来描述算法,也用来描述繁殖过程(如细胞型自动机和网络型自动机)。有限自动机是一种控制状态有限、符号集有限的自动机,是一种离散输入输出系统的数学模型。可将有限自动机设想成由一条划分为许多方格的输入带和一个控制器组成的机器:在输入带的每一个小格中可以容纳一个符号,这些符号取自一个有限符号集S-控制器具有有限个可能状态(构成集合Q)。并在每一时刻仅处于其中的一个状态q;控制器有一个读入头,可以从输入带中读入符号;时间是离散的,初始时控制器处在状态;控制器的功能是根据其当前状态g和读入头从输入带上得到的符号a,来确定控制器的下一时刻的状态实现从状态q到状态q',实现从状态q到状态铲q'的转移,并将读入头右移一格。控制器另一功能是识别终止状态(它们构成Q的一个子集F),也可将该识别功能视为有限自动机的输出。从数学上来定义,有限自动机是一个五元组:FAQSqF,,,,,,,,0QS其中,是控制器的有限状态集、是输入符号约有限集、δ是控制状态转移QQqS规律的×到的映射(可用状态转移图或状态转移表表示),是初始状态、0F是终止状态集。若δ是单值映射,则称M为确定性有限自动机;若δ是多值映射,则称M为非确定性有限自动机。,甚至近乎模糊的构成条件。但作为一个数理模型,元胞自动机有着严格的科学定义。同时,元胞自动机是一个地地道道的“混血儿”。是物理学家、数学家,计算机科学家和生物学家共同工作的结晶。因此。对元胞自动机的含义也存在不同的解释,物理学家将其视为离散的、无穷维的动力学系统;数学家将其视为描述连续现象的偏微分方程的对立体,是一个时空离计算机科学家将其视为新兴的人工智能、人工生命的分支;而生散的数学模型;物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义:、有限状态的元胞组成的元胞空间上,并按照一定局部规则,在离散的时间维上演化的动力学系统。具体讲,构成元胞自动机的部件被称为"元胞",每个元胞具有一个状态。这个状态只琵取某个有限状态集中的一个,例如或"生"或"死",或者是256中颜色中的一种,等等;这些元胞规则地排列在被你为"元胞空间"的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新,也就是说,一个元胞在某时刻的状态取决于、而且仅仅家决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新,整个元胞空间则表现为在离散的时间维上的变化。