初等元胞自动机的演化复杂性研究

发布时间：2021-02-22 08:34

　　自然界存在着许许多多的复杂系统，这些系统的每一部分结构可以非常简单，但由于各部分之间存在着一定的关联（耦合），最后表现出的整体性态可以极其复杂。元胞自动机就是研究复杂系统的理想化的一种数学模型，它最早是由Von Neumann在研究生命系统的自我复制现象时提出的，后来被广泛地用于模拟多种自然现象和生命现象。本文以形式语言理论和符号动力学为工具研究126号和122号初等元胞自动机的演化语言的复杂性。证明了：（1）126号初等元胞自动机的1-演化语言是正规的；而n-演化语言（n≥2）不是正规的。（2）122号初等元胞自动机1-演化语言是正规的；而n-演化语言（n≥2）是上下文有关语言，但不是上下文无关语言。 

【文章来源】：苏州大学江苏省

【文章页数】：37 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 元胞自动机简介
    1.1 引言
    1.2 元胞自动机的定义
    1.3 元胞自动机的极限语言和演化语言
    1.4 演化语言的等价定义
第二章 形式语言与自动机
    2.1 基本概念
    2.2 四类语言和四类自动机
第三章 126号初等元胞自动机的复杂性分析
    3.1 定理3.1的证明
    3.2 定理3.2的证明
第四章 122号初等元胞自动机的复杂性分析
2的研究">    4.1 E₂的研究
    4.2 定理4.3的证明
第五章 结论和展望
参考文献
致谢
详细摘要


【参考文献】：
期刊论文
[1]122号元胞自动机的演化语言复杂性[J]. 江志松.  华东理工大学学报(自然科学版). 2006(04)



本文编号：3045724