论文摘要
膜计算是自然计算的一个分支,它是从生物活细胞的功能与结构中抽象出来的一种计算模型,该模型具有嵌套式的分布结构。神经元是一类特殊的细胞,神经元相互连接成网络,神经系统的结构和功能与细胞有很大的区别。近年来,在膜计算模型的框架基础上,根据生物神经系统的网络特点和电信号传递的特性,M. Ionescu等人建立了神经膜计算模型(SN P系统)。SN P系统被提出以后,受到众多学者的关注。本文研究SN P系统的计算模式以及在相应计算模式下的计算能力。主要研究内容如下:一、在SN P系统中,如果神经元中存在若干条可以同时被使用的计算规则,那么计算规则的选择是非确定性的。因此,对于一个非确定性的系统,神经元中需要存在许多条可以同时被使用的计算规则。如何使神经元中计算规则的数目达到最少?针对这个问题,本文考虑一种新的规则使用方式:系统中的规则不发生改变(包括激发规则、遗忘规则),但是采用最小并行使用规则的方式。例如,如果神经元中的一个规则在一步中可以同时被激发许多次,那么,至少将该规则使用一次。这样,在神经元中每一步中使用一个规则的次数可以是任意的,产生的全部的神经脉冲会传递给与该神经元相连的所有的神经元。以这种方式,神经元只需要一条计算规则就能实现系统的非确定性,减少了神经元中计算规则数目。在该新计算模式下,证明了SN P系统仍然具有计算通用性,也就是说,具有不比图灵机差的计算能力。二、SN P系统中有几种计算规则,这些计算规则并不是总是必要的,考虑对模型计算规则增加限制条件,通过消除延时或遗忘规则等来简化模型,是一个SN P系统研究中重要的课题。本文在最小并行使用规则的SN P系统研究的基础上,提出了最小并行使用规则的SN P系统范式( SN nmoirn P系统)。即在计算规则的设计上增加了一些限制条件:去掉了延时和遗忘规则。考察了SN nmoirn P系统的性质,证明在没有延时和遗忘规则的情况下新模型也是计算通用的。最后,本文研究了含有特定数目神经元的SN nmoirn P系统与有限数字集合NFIN及半线性集合SLIN1的关系。