数值P系统的计算性能研究

摘要

膜计算是自然计算的一个分支，主要研究如何基于细胞的结构和功能（包括组织、器官、细胞群和大脑中细胞间的通信与合作机制）抽象出计算模型，并分析模型的计算能力和计算效率。膜计算领域的计算模型称为膜系统或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系统而言，变量可以迁移的特性都能提高原系统的计算能力，如系统使用更少数量的膜，使用更简单的生产函数（对多项式而言，次数更低，所含变量个数更少），使用更少数目的变量就能够达到通用。

目录

声明

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 预备知识

1.4 研究内容与创新点

1.5 本文的内容安排

2 酶数值P系统产生数值的计算能力对工作模式的鲁棒性

2.1 非确定型串行酶数值P系统的计算能力

2.2 确定型串行酶数值P系统的计算能力

2.3 本章小结

3 酶数值P系统产生数值的计算能力对酶变量数目的鲁棒性

3.1 含一个酶变量的通用全并行酶数值P系统

3.2 至多含2个酶变量的通用1-并行酶数值P系统

3.3 本章小节

4 规则带阈值对数值P系统产生数值计算能力的提升

4.1 带阈值的数值P系统

4.2 带下阈值的数值P系统的计算通用性

4.3 带上阈值的数值P系统的计算通用性

4.4 本章小结

5 分配系数为函数对数值P系统产生数值计算能力的提升

5.1 带动态分配协议的数值P系统

5.2 全并行带动态分配协议的数值P系统的计算能力

5.3 串行带动态分配协议的数值P系统的计算能力

5.4 本章小结

6 数值P系统产生语言的计算能力

6.1 作为语言产生装置的数值P系统

6.2 非酶数值P系统产生语言的能力

6.3 纯酶数值P系统产生语言的能力

6.4 酶数值P系统产生语言的能力

6.5 本章小结

7 变量的迁移特性对数值P系统产生数值和语言能力的提升

7.1 带迁移变量的数值P系统的定义

7.2 带迁移变量的数值P系统产生数值的能力

7.3 带迁移变量的数值P系统产生语言的能力

7.4 本章小节

8 总结与展望

8.1 全文总结

8.2 尚待研究的工作

致谢

参考文献

附录1 攻读学位期间发表的学术论文

附录2 博士学位论文章节内容与博士期间论文的关系

附录3 攻读博士学位论文期间参加的科研课题