论文部分内容阅读
经过近几十年的发展,人们希望第四代计算机(即超大规模集成电路计算机)具有更多的类似人的智能,于是开始寻找第五代的计算机来取代它们,例如:生物计算机,量子计算机等。其中膜计算是生物计算的重要分支,它通过模拟细胞及其组织的结构与功能,构造出具有分布式结构的并行计算模型。我们研究的是其中一种网状膜系统,即脉冲神经膜系统。这种膜计算模型源自于生物神经系统中神经元通过突触传递脉冲交换信息的机制。本文通过结合形式语言和自动机理论,从语言的产生能力、计算通用性和有效性以及数的识别能力几方面,对多种具有其它生物特性的脉冲神经膜系统进行了研究,主要工作如下:针对神经元周围的星状神经胶质细胞可以对神经元间的相互左右产生重要影响的现象,本文建立了一种具有星细胞的脉冲神经膜系统。通过模拟注册机,证明了在同步模式下,该系统可实现计算通用性。如果我们限制系统中每个神经元中的脉冲数目,那么该系统可以刻画自然数的半线性集合。另外在异步工作模式下,这种神经元和星细胞结合起来的新系统也是等价于图灵机的。这些结果表明,尽管神经元很简单,但是它组成的网络却可以具有很强的计算能力。针对Ibarra等人提出的,使用标准规则的异步脉冲神经膜系统是否具有通用性的公开问题,本文提出了一种具有激发时限的异步模式,在此模式下,所有的激发规则都具有同一个激发时限,我们通过模拟注册机,证明了使用标准规则的脉冲神经膜系统可以达到计算通用性,解决了公开问题。在经典的脉冲神经膜系统中,判断一条激发规则的使用与否,有时可能是NP困难的,这在某种程度上也不符合生物神经系统的现实。本文引入细胞膜电势来代替脉冲值,建立了一种新的规则判断方式,避免了大量的计算损耗。另外用有理数取代自然数来表示各种参数,使系统可以处理跟有理数有关的问题,提升了系统的功能与计算能力,扩大了解决问题的范围。通过模拟注册机,我们证明了这种带权值的脉冲神经膜系统可以实现计算通用性,并能求解计算困难问题。该系统使用自然数来表示各种参数时,只能刻画数字的半线性集合。针对脉冲神经膜系统的计算效率问题,我们分别使用生物里面神经元分裂和芽殖的特性创建了两种新的系统,来生成所需的计算空间,从而实现空间换时间。本文证明这两种系统可求解著名的NP完全问题,可以在多项式时间内求解给定规模的NP完全问题的所有算例。