论文部分内容阅读
膜计算是自然计算的一个分支,主要研究如何基于细胞的结构和功能(包括组织、器官、细胞群和大脑中细胞间的通信与合作机制)抽象出计算模型,并分析模型的计算能力和计算效率。膜计算领域的计算模型称为膜系统或P系统。膜计算领域的一个最重要课题就是研究各种膜系统的计算能力。数值P系统是一种重要的膜系统,对影响其计算能力的因素的研究具有重要的理论意义。 本文主要研究数值P系统各组成要素对其计算能力(包括产生数值和语言)的影响。构成一个数值P系统的主要要素有膜结构,膜中数值变量和演化规则,其中演化规则由生产函数和分配协议构成。本文主要考察的因素有规则的运行方式(串行、全并行和1-并行),酶变量的数量,阈值控制条件,函数型分配协议系数,变量的迁移特性等。主要工作如下: 研究了工作模式对酶数值P系统计算能力(产生数值)的影响。酶数值P系统在全并行和1-并行工作模式下已经被证明可以达到通用,但在串行模式下能否达到通用还是个公开问题。本文证明了酶数值P系统在确定型串行工作模式下能够达到计算通用性,改进了一个已知的非确定型数值P系统的通用性结果(在系统其他参数不变的情况下,所用的膜数量更少,生产函数所用变量数目更少)。上述结果表明酶数值P系统的计算能力对工作模式具有鲁棒性,即不管采用何种工作模式酶数值P系统都能达到通用性。 研究了酶变量的数量对酶数值P系统计算能力的影响。酶数值P系统在全并行和1-并行工作模式下已经被证明可以达到通用,但系统最少使用多少个酶变量就能达到通用还没有相关研究。本文证明了对于酶数值P系统作为识别装置,在全并行和1-并行运行模式下最少只要1个酶变量就能达到通用;作为产生装置,在1-并行模式下,最少2个变量可以达到通用。这些结果说明,系统的计算能力对酶变量数量具有鲁棒性,即使将酶变量的数目减少到1个系统仍然可以达到通用。 研究了带阈值的规则对数值P系统计算能力(产生数值)的影响。对数值P系统的规则没有任何限制时在全并行和1-并行下计算能力能否达到通用是个公开问题。本文证明了带阈值的数值P系统在全并行和1-并行两种工作模式下都能够达到通用性,即使把它们的膜数量限制为1,生产函数限制为线性函数。以上结果表明对规则的使用加阈值控制策略能够增加系统的计算能力。 研究了函数型分配协议系数对数值P系统计算能力(产生数值)的影响。数值P系统的分配协议系数为常数时计算能力能否达到通用是一个公开问题。本文将常数系数扩展到函数,分配系数函数的函数值决定变量分得的份额,所得到的系统称为带动态分配协议的数值P系统。证明了带动态分配协议的数值P系统在全并行工作模式下,使用常值函数作为生产函数,单变量线性函数作为分配系数函数,只含一个膜的系统可以达到通用。而在串行工作模式下,生产函数为至多含一个变量的线性函数,分配系数为至多含两个变量的线性函数,只含一个膜的系统也可以达到通用。这些结果表明分配协议系数由常数拓展到函数可以增加系统的计算能力。 研究了数值P系统产生语言的能力。系统产生语言的能力是研究系统计算能力的基本问题之一。目前还没有相关文献研究数值P系统产生语言的能力。本文给出了数值P系统产生语言的定义,并研究了数值P系统,酶数值P系统,纯酶数值P系统在1-并行工作模式下产生语言的能力,以及上述系统产生的语言与有限语言,正则语言,上下文无关语言以及递归可枚举语言之间的关系。 研究了变量的迁移特性对数值P系统计算能力(产生数值和语言)的影响。把一般P系统符号对象可以在膜内外迁移的特性引入到数值P系统,提出了带迁移变量的数值P系统,并研究了其作为数值产生器产生数集和语言产生器产生语言的能力,证明了其作为数值产生器可以达到通用性,作为语言产生器,将其产生的语言与乔姆斯基层次中的语言进行了比较,并刻画了递归可枚举语言。获得的结果表明,不论是对数值P系统还是对酶数值P系统而言,变量可以迁移的特性都能提高原系统的计算能力,如系统使用更少数量的膜,使用更简单的生产函数(对多项式而言,次数更低,所含变量个数更少),使用更少数目的变量就能够达到通用。