脉冲神经膜系统的计算能力研究

论文摘要

硅基微电子器件线宽小于10纳米以后，来自器件工作原理、工艺技术与制造成本等方面的限制将形成难以克服的障碍。突破硅基器件的框框，发展非传统的新技术是当前计算机科学领域的研究前沿和热点。膜计算是非传统计算领域之一。膜系统，也称P系统，是一类分布式并行计算模型。该类计算模型主要是受细胞、组织、器官或其它生物结构处理化学物质的方式启发而建立起来的。由于其良好的计算性能以及在语言学、图形学、系统生物学、组合优化等领域的广泛应用价值，受到许多学者的关注。本文研究一类特殊的P系统，即脉冲神经膜系统，简称SNP系统。它是基于大脑中神经元之间通过突触相互协作、处理脉冲信息的生物现象而抽象出来的一种新计算模型。论文从语言(或数的)产生能力、小通用性以及计算有效性三个方面研究了脉冲神经膜系统的计算能力，主要工作如下：首先研究了脉冲神经膜系统的语言(或数的)产生能力。计算设备的语言(或数的)产生能力是研究计算设备计算能力的基本问题之一。关于脉冲神经膜系统，本文研究了三类具体系统的语言(或数的)产生能力，即穷举使用规则的脉冲神经膜系统、非同步脉冲神经膜系统以及轴突膜系统。对于穷举使用规则的脉冲神经膜系统，在限制性和非限制性两种语言的定义下，分别研究了它在使用延展规则时的语言产生能力。在两种情形下，都证明了延展脉冲神经膜系统在穷举使用规则模式下可以刻画有限语言和递归可枚举语言，同时还研究了与正则语言的关系。由于在非同步模式下，考虑系统的计算时间是没有意义的，因此在非同步脉冲神经膜系统中只能定义非限制性语言。在这种语言定义下，研究了非同步脉冲神经膜系统在使用延展规则时的语言产生能力，得到具有延展规则的非同步脉冲神经膜系统可以刻画有限语言和递归可枚举语言，同时还研究了它所产生的语言与正则语言以及非半线性语言的关系。另外，分别研究了轴突膜系统作为数的产生装置和语言产生装置时的产生能力：作为数的产生装置，得到了轴突膜系统产生的数集与有穷数集和半线性数集的关系；作为语言产生装置，得到了轴突膜系统产生的语言与有限语言和上下文无关语言的关系。其次对脉冲神经膜系统的小通用性进行了研究。计算模型的小通用性是计算机科学中经典的研究问题之一。对于脉冲神经膜系统而言，研究小通用性问题除了计算机科学意义外，还有其生物学意义：给出某种小通用“脑”的度量。本文对脉冲神经膜系统的小通用性进行了如下研究：针对A．P(?)un等人所构造的小通用脉冲神经膜系统，讨论了如何优化它们所使用的神经元个数的问题，提出了加法模块、减法模块以及加法与减法模块之间在一定情形下可以共用附属神经元的思想。通过详细分析任两个指令所对应的模块可以共用附属神经元的各种情形，把所模拟的小通用注册机的指令进行分类，使每组指令共用相同的附属神经元，从而得到了具有更少神经元个数的小通用脉冲神经膜系统。另外，在作为计算函数的装置和产生数的装置两种情形下，本文分别构造了穷举使用规则的小通用脉冲神经膜系统，并通过考虑附属神经元共用的情形，优化了所得到的小通用性系统的神经元个数。最后研究了脉冲神经膜系统的计算有效性。由于脉冲神经膜系统的拓扑结构是固定的，在计算过程中无法由脉冲神经膜系统本身来生成计算空间，从而实现空间换时间。因此，本文研究了脉冲神经膜系统在使用指数规模的预计算资源(即系统包含指数个神经元)时的计算有效性。利用这种类型的系统，给出了一族求解QSAT问题的脉冲神经膜系统(QSAT问题是PSPACE完全问题)。在该族脉冲神经膜系统中，每个脉冲神经膜系统可以在多项式时间内(与问题规模相关)求解具有某一相同规模的QSAT问题的所有算例。

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 预备知识
• 1.2 研究背景、目的及意义
• 1.3 膜系统简介
• 1.4 脉冲神经膜系统
• 1.5 研究思路与创新点
• 1.6 本文的内容安排
• 2 穷举使用规则的脉冲神经膜系统的语言产生能力
• 2.1 穷举使用规则的脉冲神经膜系统
• 2.2 穷举使用规则的脉冲神经膜系统的语言产生能力
• 2.3 本章小结
• 3 非同步脉冲神经膜系统的语言产生能力
• 3.1 非同步脉冲神经膜系统
• 3.2 非同步脉冲神经膜系统的语言产生能力
• 3.3 本章小结
• 4 轴突膜系统的数和语言的产生能力
• 4.1 轴突膜系统
• 4.2 轴突膜系统的数的产生能力
• 4.3 轴突膜系统的语言产生能力
• 4.4 本章小结
• 5 小通用脉冲神经膜系统的改进
• 5.1 具有标准规则的计算型小通用脉冲神经膜系统
• 5.2 具有延展规则的计算型小通用脉冲神经膜系统
• 5.3 产生数的小通用脉冲神经膜系统
• 5.4 本章小结
• 6 穷举使用规则的小通用脉冲神经膜系统
• 6.1 穷举使用规则的计算型小通用脉冲神经膜系统
• 6.2 穷举使用规则的产生数小通用脉冲神经膜系统
• 6.3 本章小结
• 7 具有预计算资源的脉冲神经膜系统求解QSAT问题
• 7.1 QSAT问题的求解
• 7.2 一个例子
• 7.3 本章小结
• 8 总结与展望
• 8.1 全文总结
• 8.2 尚待研究的工作
• 致谢
• 参考文献
• 附录1 攻读学位期间发表的学术论文
• 附录2 博士学位论文章节内容与博士期间发表论文的关系
• 附录3 攻读博士学位论文期间参加的科研课题