论文部分内容阅读
随着微电子技术的发展进入瓶颈,一些非传统计算模型的探索与研究开始引起人们更多地关注,比如量子计算、生物计算等。膜计算由G. P?aun院士受到细胞处理化学物质的机理启发而提出,它属于生物计算。该模型是一种分布式并行的计算模型,也称它为P系统。由于它具有较好的计算性能及潜在的应用价值,该方向已成为计算机科学领域快速发展的新兴领域之一。本文研究的是一类基于生物神经细胞的特殊P系统,即基于脉冲数目的串行脉冲神经P系统。 在计算机科学中,对于新型计算模型的探索,首先要保证它的通用性,即与图灵机的等价,然后考虑在不降低模型的计算能力的情况下,使模型的结构尽可能简化,且使用较少的计算资源。本文在基于脉冲数目的串行脉冲神经P系统中引入均质性、反脉冲等生物特征,研究对应系统的计算通用性;构建小通用串行脉冲神经P系统,研究串行系统的范式,并探讨了系统产生语言的能力。主要工作如下: 在基于最小脉冲数目的串行脉冲神经P系统中,将计算结果定义为输出(或输入)神经元输出(或输入)前两个脉冲之间的时间间隔,证明了使用最小串行策略或最小伪串行策略的不带时延的脉冲神经P系统是通用的数字产生装置和接受装置,得到的结果解决了O.H. Ibarra等人留下的两个问题:(1)当计算结果不是通过停机计算时的脉冲数目来定义,而是采用经典的用输出两个脉冲的时间间隔来定义,使用最小串行策略的脉冲神经P系统是否还是通用的?(2)使用最小伪串行策略的脉冲神经P系统是否是通用的? 对小通用计算系统的研究一直是计算机科学中的一个热点问题,在作为计算函数的装置和产生数集的装置两种情形下,通过对模拟的通用注册机中指令的优化,分别构造了一个用于计算函数的含有137个神经元的基于最小脉冲数目的不带时延的小通用串行脉冲神经P系统和一个产生数集的含有126个神经元的基于最小脉冲数目的不带时延的小通用串行脉冲神经P系统,得到的结果表明由少量的神经元组成的系统就具有相当强的计算能力。 均质性是许多计算装置都具有的重要特性之一,本文在基于最大脉冲数目的串行脉冲神经P系统中引入均质性和带权值的突触,研究这类系统的通用性。证明了作为数的产生装置和接受装置,使用最大串行策略或最大伪串行策略的不带时延的带权均质脉冲神经P系统都是通用的;通过移除系统中的大于1的突触权值,我们还证明了使用突触权为1的均质脉冲神经P系统在最大伪串行模式下也是通用的。这些结果意味着神经系统的结构是关键性的。 对基于最大脉冲数目的串行脉冲神经P系统的若干范式进行了研究,即构造结构尽可能简化的系统。通过引入若干“辅助神经元”和“延时神经元”,证明了不带时延的使用最大伪串行策略的脉冲神经P系统在产生模式和接受模式下的最大入度和最大出度均不超过2;在仅使用简单神经元(只有一条规则)的情况下,证明了不带遗忘规则的使用最大串行策略的简单脉冲神经P系统作为数的产生装置是通用的;在最大伪串行策略下,不带遗忘规则和时延的几乎简单脉冲神经P系统作为数的产生装置是通用的,不带遗忘规则和时延的简单脉冲神经P系统作为数的接受装置也是通用的。这些结果改进了G. P?aun和O.H. Ibarra等人的已有结果。 在基于最大脉冲数目的串行脉冲神经P系统中引入反脉冲和抑制突触,研究了基于最大脉冲数目的带反脉冲的串行脉冲神经P系统的计算能力,分别构造了利用激发规则产生反脉冲和利用抑制突触将脉冲转变为反脉冲的串行脉冲神经P系统,证明了使用最大串行或最大伪串行策略的带反脉冲的脉冲神经P系统,在产生模式和接受模式下都是通用的。 对基于最大脉冲数目的串行脉冲神经P系统的语言产生能力进行了研究,讨论了该系统产生的二进制符号串语言和有限语言及正则语言的关系,并证明了基于最大脉冲数目的串行脉冲神经P系统可以刻画递归可枚举语言。