元胞自动机生成的时间序列的复杂性研究

摘要

元胞自动机是自然界许多复杂系统的理想化数学模型，它可以模拟许多自然现象与生命现象，大量未解决的问题为这个困难而有趣的领域展现了广阔前景.　　自vonNeumann首次提出元胞自动机的思想至今已有半个世纪，学者们对元胞自动机进行了大量研究，然而现在对元胞自动机仍然缺少有效的数学方法，严格的数学结果也很少. 本文探求一种新的研究元胞自动机的方法，使用禁止字理论、计算机搜索和符号动力学的方法对于256个初等元胞自动机生成的时间序列(只观察一个位点上的演化所得到的序列)进行复杂性分析.借助时间序列所具有的特性通过研究它的禁止字来研究演化语言(本文所指的演化语言如无特别标注都是指宽度为1的时间序列所组成的语言)，确定了大多数初等元胞自动机生成的时间序列所处的Chomsky层次以及严格的数学表达式.　　在对初等元胞自动机时间序列的禁止字分析之后，按照它们演化语言的复杂程度分为以下四类：第Ⅰ类为满射，第Ⅱ类为有限补正规语言，第Ⅲ类为无限补正规语言，第Ⅳ类很有可能是非正规语言.　　第Ⅰ类情况中的初等元胞自动机没有禁止字，其宽度1的演化语言为最大可能的正规语言，并且这一类中部分元胞自动机的任意宽度演化语言都是正规的.　　第Ⅱ类情况中的初等元胞自动机只有有限多个禁止字，因此其宽度1的演化语言为有限补正规语言.　　第Ⅲ类情况中的初等元胞自动机有无限多个禁止字，但禁止字集是正规语言，经过理论分析知道其演化语言为无限补正规语言.此类情况中一个代表性的例子是27号初等元胞自动机.　　第Ⅳ类情况中的初等元胞自动机也有无限多个禁止字，但是它们的演化语言很有可能不是正规语言，这类情况比前三种情况复杂的多，对这一类初等元胞自动机的讨论尚未全部完成.本文给出了其中56号初等元胞自动机的宽度为1的演化语言是上下文无关语言的详细证明，并给出了严格的数学表达式.

目录

文摘

英文文摘

第一章元胞自动机简介

1.1引言

1.2元胞自动机的定义

1.3元胞自动机的分类问题

1.4元胞自动机的极限语言和演化语言

第二章时间序列的复杂性分析

2.1引言

2.2禁止字

2.3计算机搜索

2.4第Ⅰ类：满射

2.4.1子类Ⅰ.1

2.4.2子类Ⅰ.2

2.5第Ⅱ类：有限补正规情况

2.6第Ⅲ类：无限补正规情况

2.7第Ⅳ类：非正规情况

2.8 讨论

第三章27号元胞自动机

3.1引言

3.2定理3.1的证明

第四章56号元胞自动机

4.1引言

4.2用计算机进行搜索的实验结果

4.3主要结果

4.4定理4.1的证明

4.5定理4.2和定理4.3的证明

附录A形式语言与自动机理论介绍

A.1引言

A.2基本概念

A.3四类语言与四类自动机

A.4正规语言与有限自动机

参考文献

发表文章目录

致谢