【作者】 秦大康；

【导师】 谢惠民；

【作者基本信息】 苏州大学 ， 应用数学， 2005， 博士

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

【Abstract】 Cellular automata are ideal mathematical models of complex systems in nature, They can emulate lots of phenomenon in nature and life phenomena. Many unsolved questions in this difficult and interesting field show great prospect in the future.It has passed half a century since von Neumann first proposed the idea of cellular automata, scholars have made lots of research to cellular automata, however there are few efficient methods to study cellular automata, and the strict mathematical results are also few. This article explores a new kind of method to study cellular automata, in which by using distinct excluded blocks theory, computer search and symbolic dynamics to study the time series (the series generated at one site in the course of evolution) generated by 256 elementary cellular automata. Using the character of time series, we can study their evolution language (in this article without special remark the evolution language’s width is always 1) by study their distinct excluded blocks, and pinpoint their Chomsky level and strict mathematical expression of the time series generated by most elementary cellular automata.After studying the time series generated by elementary cellular automata, according to the complexity of their evolution language we can classify them into four classes: I class of surjective, II class of finite complement regular languages, III class of infinite complement regular languages, and IV class which are probably unregular languages.Class Ⅰ: the cellular automata in this class have no distinct excluded blocks, their evolution languages are the largest regular languages, and for some of them the evolution languages with any width are also regular.Class Ⅱ: the cellular automata in this condition have finite distinct excluded blocks, and we can know their evolution languages are finite complement regular.Class Ⅲ: the cellular automata in this condition have infinite distinct excluded blocks. After theoretical analysis we can show that their evolution languages are regular. An example is rule 27 ECA.Class Ⅳ: the cellular automata in this condition also have infinite distinct excluded blocks, and their evolution languages are probably not regular languages. This class is much more complex than other classes. The discussion for this class is not completed yet. In this article we prove that the evolution language of rule 56 ECAwith width 1 is context-free language, and obtain the evolution language’s strict mathematical expression.更多还原