（计算机软件与理论专业论文）尖峰神经元p系统.pdf

中山大学学位论文尖峰神经元p 系统 尖峰神经元p 系统 计算机软件与理论 袁志敏 张治国副教授 摘要 尖峰神经元p 系统( 简称s np 系统) 是基于生物神经元结构及功能提出的 一种并行计算模型。该模型于2 0 0 6 被首次提出，它与传统的p 系统相比，有结 构简单，计算能力强等特点。s np 系统的计算需要全局时钟的控制。它可作为 数字或语言的产生器并存在多种计算模式。 本文在原有s n p 系统的基础上提出了一种新的计算模型带启动子的异 步s np 系统。该系统与原有的s np 系统相比最大的不同在于新系统中不存在 全局时钟。它是通过启动子的引入，实现各神经元间的同步工作。本文通过用该 系统模拟寄存器工作方式的方法证明了当该系统作为数字产生器时，它具备和图 灵机一样的计算能力。本文还通过用该系统模拟正则文法产生语言的过程的方法， 证明了当该系统作为语言产生器时，存在一个映射，使得任意正则语言集都包含 于该系统所产生的语言集的象之中。 本文的另一项主要工作在于引入了另一种语言产生方式：将输入神经元是 否接收尖峰的情况作为s np 系统所产生的语言。文中还证明工作在该语言产生 模式下的s np 系统所产生的语言集经过映射后与正则语言集相等。此外，本文 还给出了将任意工作在该模式下的s np 系统转化为有限自动机的方法，并用c 语言实现由己知系统到其转移格局的转换过程。 关键词：异步尖峰神经元p 系统，尖峰神经元p 系统，膜计算，产生语言 中山大学学位论文 尖峰神经元p 系统 s p i k n gn e u r a lps y s t e m3 p l k l n gn e u r a irs y s t e m s o f 细a r ea n dt h e o r e t i c a ic o m p u t e rs c i e n z h i m i ny u a n s u p e r v i s o rz h i g z h a n g a b s t r a c t s p i l 【i n gn e u t r a lps y s t e m ( s nps y s t e m ) i sap a r a l l e lc o m p u t i n gm o d e lb a s e do n t h es t m c t u r ea n df u n c t i o no fb i o l o 酉c a ln e u r o n nw a sf i 】噶t l yi n t r o d u c e di n2 0 0 6 p a r i n gt ot h ep r e v i o u sps y s t e m ，i th 觞s i m p l e rs t m c t u r eb u ta l s o 嗍l ss t r o n g c o m p u t a b i l i t y s nps y s t e m 、釉r k su n d e rau n i v e r s a lc 1 0 c ka n di t c a i la c tb o t h 弱 肌m b e ra n dl a n g l l a g eg e n e r a t o ri nd i 疵r e n tm o d e s an e wc i a s so fp a r a l l e lc o m p u t i n gd e v i c e sc a l l e da s y n c h r o n o u ss p i l 【i n gn e u r a lp s y s t e m sw i t hp r o m o t e r si si n t r o d u c e d u n l i k et h er e g u l a rs p i l 【i n gn e u r a lps y s t e m s ， t h e yw o r kw i t h o u th e l po ft h eu i l i v e r s a lc l o c kb u tt h e yi i l c l u d eas e to fp r o m o t e l l s t h e c o m p u t i n gp o w e ro ft h e s es y s t e m si sp r o v e dt ob et h r i n gc o m p l e t ew h e nt h e ya r e c o n s i d e r e da sn u m b e rg e n e r a t o r s w h e nt h e ya r ec o n s i d e r e da s1 a n g u a g eg e n e r a t o r s ，i t i sp r o v e dt h a ta n yr e g u l a rl a n g u a g ec a i lb eac o d i n gm o r p h i ci m a g eo ft h eg e n e m t e d l 加g u a g eo fa na s y n c h r o n o u ss p i l 【i 】唱n e u r a lps y s t e m an e ww a yt 0g e n e r a t el a n g l l a g ei ns nps y s t e mi sa l s oi n t r o d u c e di nt h ep a p e r 而el a n g t l a g eg e n e r a t e db yt h es y s t e mi sc o n s i d e r e dt 0b et h es p 像et r a 纽a c c e p t e db y t h ei 1 1 p u tn e u r o n nh a sa l s ob e e np r o v e dt h a tt h ei i e r s e - m o r p l l i ci l l l a g eo fs u c h l a n g u a g ei st h er e g u l a rl a n g l l a g e i na d d i t i o n ，t h em e t h o df o rt r a n s f e r r i n gs u c hs y s t e m i n t on e ai si n t r o d u c e d 锄dt h et r 锄s f o 姗a t i o nf 幻mac e r t a i ns nps y s t e m si 】缸t i a l c o 碰伊r a t i o nt o 抵t r a n s i t i o nc o 瓶g u r a t i o ni si n l p l e m e n t e db ycl a n g i l a g e k e yw o r d s ：a s y n c h r o n o u s ，s p i k i n gn e u r a lps y s t e m ，m e m b r 姐ec o m p u t i n 舀g e n e r a t e d l a n g u a g e 中山大学学位论文尖峰神经元p 系统 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：弓乙吝刍久 日期：入坶孑年f 月莎日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：袁胁 日期伽苫年s 月箩日 导师签名锨蜩 日期：缈乎年f 月8 日 中山大学学位论文 尖峰神经元p 系统 1 1 研究背景 第1 章引言 p 系统( 也称膜计算) 是一种分布式的并行计算模型。该理论作为自然计算 的一个分支首次由自罗马尼亚科学家g h e o r g l l ep a u n 于1 9 9 8 提出。 膜计算的本质是从活细胞以及由细胞组成的组织或器官的功能和结构中抽 象出模型或计算思想。由于这种系统是以最大并行的方式完成，它的计算效率将 远远超过现有的电子计算机。膜计算系统的理论模型不但具有图灵机一样的计算 能力，甚至还有可能超越图灵机的局限。 目前，膜计算的研究还处于初始阶段。研究者们主要通过用数学，形式语言 等工具来进行膜计算的理论研究，提出了各种膜计算模型，并证明了大多数模型 都具有图灵机一样的计算能力；研究了可计算性及其计算复杂性。膜计算可应用 领域广泛，如：生物学，计算机图形学，语言学，理论计算机，管理等。尽管膜 计算的理论发展迅速，理论上的应用研究也很多，但是还没有关于膜计算应用于 实际工程的文献发表。 2 0 0 0 年，g h e o r g l l ep a u n 首次公开发表了关于膜计算的文献【1 1 。同年1 0 月， p a u n 的另一篇成为2 0 0 3 年被引用率最高的文献之一【2 1 。膜计算已经成为一个新 兴的研究领域。目前的研究成果主要集中在欧洲。国内研究学者不多，主要有华 中科技大学的潘林强教授，中科院软件所的陈海明研究员和上海交通大学的尤晋 元教授等。以上学者均在膜计算领域取得了较好的研究成果【3 1 。 1 2 问题陈述 1 2 1 相关文献综述 近年来，有关尖峰神经元p 系统( 简称s np 系统) 的研究已成为p 系统研 究领域的一个热点问题。尖峰神经元p 系统与传统p 系统相比，有规则简单， 反应物单一的特点，但与传统p 系统一样具备强大的计算能力( 多数尖峰神经元 系统已被证明具有图灵机一样的计算能力) 。 1 中山大学学位论文尖峰神经元p 系统 尖峰神经元p 系统的结构为有向图结构，其中，系统中的神经元对应于有向 图中的结点，用于连接各神经元的突触对应于有向图的边。各神经元中均包含着 尖峰和规则这两个基本要素。若在某个神经元中尖峰的个数满足规则所需的使用 要求，那么该规则将会被使用，且使用该规则产生的新的尖峰将会被发射到邻接 神经元中去，作为其下一时钟周期的反应物质。系统的运算是在时钟的控制下进 行的，所有神经元是以同步的，并行的方式进行工作的。 尖峰神经元p 系统作为一种计算模型，既可以是数字产生器，也可是语言产 生器。 当尖峰神经元p 系统作为数字产生器是，系统的计算结果可用输出神经元两 次向环境发射尖峰的时间间隔表示。工作在这种模式下的系统是图灵完全的。并 且该系统产生的语言集与有限语言集，正则语言集及递归可枚举语言集之间存在 一定的关系【5 1 。此外，尖峰神经元p 系统作为数字产生器工作在其它模式下的情 况在文献【5 ，1 0 】中也做了简要的介绍。 尖峰神经元p 系统作为集合 0 ，1 】- 上的语言产生器，其计算结果可用两种方 式表示。一种方式是用尖峰链【6 】表示，另一种方式是用尖峰跟踪方式的表示川。 文献【6 ，7 】分别讨论了s np 系统在这两种工作模式下计算能力，证明了系统在不 同工作模式下所产生的语言集与正则语言集，递归可枚举语言集之间的关系。 1 2 2 论文主要工作 本文的主要工作在于( 1 ) 提出了一种新的s np 系统带启动子的异步尖峰 神经元系统，并证明了该系统作为数字产生器与图灵机有相同的计算能力；作为 语言产生器，存在一个映射，使得任意正则语言集都包含于该系统所产生的语言 集的象之中。( 2 ) 提出了一种不同与尖峰链和尖峰跟踪方式的另一种语言产生方 式，并证明了工作在该语言产生模式下的s np 系统所产生的语言集经过映射后 与正则语言集相等。 带启动子的异步尖峰神经元p 系统除去了传统s np 系统中的全局时钟，通 过一种引入新的物质启动子来实现系统中各神经元工作的同步。其具体作用 主要体现在规则的使用上。带启动子的异步s np 系统将规则分为两类：一类是 不带启动子的规则( 与传统s np 系统中的规则形式类似) ：另一类是带有启动子 的规则。其中，带有启动子这类规则的使用除了要满足传统s np 系统中规则使 2 中山大学学位论文尖峰神经元p 系统 用的条件之外，还需要求该规则所在的神经元中包含规则所需的启动子，而启动 子是由邻接神经元所产生的。这样，便实现系统中各神经元工作的同步。 带启动子的异步s np 系统作为数字产生器，因为没有全局的时钟，所以不 能将输出神经元两次向环境发射尖峰的时间间隔当作计算的结果【5 1 ，而是将系统 计算停止后，输出神经元中尖峰的个数作为最终产生的数字。论文通过用该系统 模拟寄存器的工作模式的方法，证明了带启动子的异步s np 系统在作为数字产 生器时，其计算能力和图灵机是等价的。带启动子的异步s np 系统还可作为语 言产生器，论文中采用的是尖峰跟踪的方式作为系统产生的语言，并且证明了存 在一个映射，使得任意正则语言都包含于带启动子的异步s np 系统所产生语言 的象之中。 本文的另一项工作是引入了一种的新的尖峰神经元系统的语言产生方式 以输入尖峰链作为系统产生语言。与现有的尖峰神经元系统产生语言方式所 不同的是工作在此模式下的系统中存在一个输入神经元。我们把该神经元从系统 初始状态到终结状态是否接受来自环境的尖峰的情况定义为系统产生的语言。本 章还证明了工作在该语言产生模式下的s np 系统所产生的语言集经过映射后与 正则语言集相等。 1 3 论文组织结构 本文共分6 章，其具体内容如下： 第2 章主要介绍了与p 系统理论相关的基础理论：字母表，乔姆斯基文法， 自动机与寄存器等概念。 第3 章主要介绍了与尖峰神经元p 系统理论中的重要定义。 第4 章引入了一种新的计算模型带启动子的异步s np 系统，并证明了 该系统作为数字产生器与图灵机有相同的计算能力，作为语言产生器与正则语言 集存在一定的关系。 第5 章引入了一种新的s np 系统语言产生模式：若输入神经元接收了来自 环境的物质，则产生1 ，否则则产生0 。本章还证明了工作在这种模式下的s np 系统所产生的语言与正则语言集存在一定的关系。 第6 章对全文做了总结，并探讨了下一阶段的研究工作。 3 中山大学学位论文 尖峰神经元p 系统 2 1 字母表 第2 章p 系统基础理论 字母表是抽象符号的有穷非空集对于字母表”用矿表示y 的所有符号串 的集合。空串记为九。从数学意义上讲，矿是y 上由连接操作生成的自由类群 ( 类群的单位元是九) 。y 上的非空串集合，即y + 一m ，记为矿，y 的语言是矿 的一个子集。不含空串的语言( 因此是矿的一个子集) 称为是k 无关的。【9 】 2 2 乔姆斯基文法 c h o m s k y 文法是一个四元g = ( ，r ，p ) ，其中，丁是不相交的字母表， s ，且p 是( u 丁) + ( u 丁) ( u 丁) + 的一个有穷子集。根据规则的形式， c h o m s k y 文法可以分类如下一个文法g = ( ，丁，s ，p ) ，称为： 单调长度增加的，若对于所有的“一y 尸都有i 训m 。 上下文相关的， 若每个“_ ，尸有“一m 4 h 2 ， ，；“1 嬲2 ，其中 比，h 2 ( u r ) 枣，4 ，x ( u 乃+ ( 在单调和上下文相关文法中，如果s 不出现在尸中规则的右端，产生式s - a 是允许的) 上下文无关的，若每个规则比呻，p 都有比。 线性的，若每个规则“_ ，尸都有砧和矿z 木u f 宰胛宰。 右线性的，若每个规则“一 ，p 都有“和，r 奎u z 木。 左线性的，若每个规则“一1 ，p 都有“和v z u 胛宰。 正则的，若每个规则“一y p 都有“和y zu 掰u u ) 。 任意文法、单调文法，上下文无关文法和正则文法分别称为0 型、1 型、2 型和3 型文法。 由单调文法产生的语言等价于由上下文相关文法产生的语言族；右线性文法 和左线性文法产生的语言族相同且等价于正则文法产生的语言族，并等价与正则 正 中山大学学位论文尖峰神经元p 系统 语言族。 分别用咫， c f 上，和尺阳表示有任意文法，上下文相关文法，上下文无 关文法，线性文法和正则文法产生的语言族( 咫表示递归可枚举) 用删表示有 穷语言族。 下面的真包含关系成立： f i nc r e g c u nc c fc c sc r e 这称为c h o m s k y 层次体系。【9 j 2 3 自动机与寄存器 自动机是与文法反向工作的语言定义装置。它由给定的字母表的字符串开 始，分析( 识别) 它们，告诉我们输入串是否属于特定的语言。 c h o m s k y 层次体系中的5 个基本语言族尬g ，三肼，c f ，c s ，舡也可以由识别 自动机刻画。这些自动机分别是：有穷自动机，单向下推自动机，下推自动机， 线性有界自动机和图灵机。这里只给出这些装置的基本变型 一个( 非确定型) 有穷自动机具有结构 m 一饭，y ，f ，6 ) ， 其中k 和y 是不相交的字母表，s o 七，fck ，且6 ：k y 呻p 僻) ；k 是状 态集，y 是自动机的字母表，是初始状态，f 是终结状态集，6 是转移映射 若c 口以 ( s ，口) ) s 1 对于所有的s k ，口矿成立，则称该自动机是确定型的在集 合k y 宰上的关系卜以下述方式定义：对于s ，s k ，口y ，x y 丰，若 s 6 ( s ，口) ，则记为( s ，甜) 卜o ：x ) 由定义，o ，a ) 卜- o ，a ) 若卜是关系卜的 自反传递闭包，则由自动机m 识别的串构成的语言定义为 l 似) = 仁y 事i 瓴，z ) 卜- 事o ，a ) ，s ， s 中山大学学位论文尖峰神经元p 系统 众所周知，确定型和非确定型有穷自动机刻画了同一类语言尺嬲若允许a 转 移，即6 定义在k 缈u a ) ) 上( 当该自动机在输入带上没有读入符号时同样能 改变状态) ，或者当输入串以双向方式被扫描( 不论是向左还是向右，都不改变 它的符号) 时，该有穷自动机的能力没有增加。【9 】 寄存器的结构为m ；沏，日，乇，厶，) ，其中，m 为寄存器的个数，日为指令标 号的集合，为开始指令的标号( 标志一条么d d 指令) 如为结束指令的标号( 被 赋给尼缸z 指令) ，为指令的集合；每一个来自日的标志，对应着唯一一条来 自，的指令。，中的指令有如下3 种形式： 劢脚似易妨( 寄存器，加1 ，程序调转到指令为知或如) 磊? 己珊p ) ，易劲( 若寄存器，不空，则寄存器，减1 ，然后程序跳转到6 ，否则 寄存器厂不变，程序跳转到指令聃。 如? 尼亿z ( 结束指令) 。 一个寄存器m 以下面的方式产生( m 数量的集合：起初，所有寄存器均 为空( 例如，存储的数量为o ) 。程序由指令如，当到达了停止指令如时，寄存 器1 中的值，l 即为m 产生的结果。( 为了不失一般性，我们可以假设寄存器1 不接收s 叩指令，只接收脚指令) 。寄存器计算能力与图灵机是等价的。 6 中山大学学位论文 尖峰神经元p 系统 第3 章尖峰神经元p 系统 本章主要介绍尖峰神经元p 系统的定义；系统语言的产生形式以及与之相对 随的定理。 3 1 尖峰神经元p 系统的定义 度数为历的尖峰神经p 系统的定义如下【5 】： 兀= ( d ，d 1 ，仃2 ，o m ，s ) ，s n o ) 其中： 1 d = 缸) 为单字母字母表( 口称为尖峰) ； 2 d 。仃m 为形如q = f ，尺f ) ，1 f m 的神经元，其中： a ) 7 t i 0 为神经元吼在初始状态中尖峰的个数； b ) 尺f 为规则的有限集合，规则的形式有如下两种： ( 1 )冒口c 一口；d ，其中c 1 ，d 0 ，e 为口的正则表达式； ( 2 ) n s 一入，其中s 1 ，且对于( 1 ) 中的任意规则e 口c n ；d ， 有口s 硭l 饵) ； 3 妙s 礼( 1 ，2 ，m ) ( 1 ，2 ，m ) ，对于任意1 f m ，有( f ，f ) 硭s y s n ； 4 o 为输出神经元的标号。 类型( 1 ) 中的规则称为发射规则，它的使用方式如下：若规则所在的神经 元中包含七个尖峰，其中七满足口r l ) 且尼c ，则规则f 口c _ n ；d 将会被使 用。该规则的使用意味着c 个尖峰将会被消耗，最终，规则所在的神经元中将剩 下七c 个尖峰。规则使用后神经元将立刻发射，并在d 个时钟周期后产生一个 尖峰。如果d = o ，那么尖峰将在规则使用的同一时钟周期产生；如果d = 1 ，那么 尖峰将在规则使用的下一个时钟周期内产生；以此类推。在d 1 的情况下，如 果神经元在第f 个时钟周期使用了该规则，那么该神经元在f ，件1 ，件2 ，f 柑1 时刻将处于关闭状态。处于关闭状态的神经元不能接收来自任何地方的尖峰。若 有尖峰尝试进入处于关闭状态的神经元，则这些尖峰将被丢失。在f + d 时刻， 神经元将再一次打开，准备接收来自邻接神经元发射的尖峰，它在该时刻接收到 7 中山大学学位论文尖峰神经元p 系统 的尖峰可于f + d + 1 时刻的使用。神经元o f 发射的尖峰将送给满足条件 ( ，j ) 夥s 扎的所有神经元a ，。若规则e 肛c - a ；d 中己( e ) = 缸c ) ，则可把规则 e 口c 一口；d 简写为n 6 - 口；d 。 类型( 2 ) 中的规则称为遗忘规则，它的使用方式如下：如果某神经元中刚 好包含s 个尖峰，那么，神经元中的规则n s - 入，将会被使用。这条规则的使用 意味着s 个尖峰将立即全部消失且不产生任何物质。 在同一时钟周期内，如果某神经元中的尖峰的个数满足发射规则的要求，那 么在此时刻一定没有满足条件的遗忘规则可以被使用，反之亦然。即对于同一神 经元内的两条规则e 口c n ；d ，口c 一入，必须满足条件口s 硭l 饵) 。但是有可能在 同一神经元中，尖峰的个数同时满足两条发射规则的要求。即存在两条发射规则 e 口c _ 口；d 1 ，f q c _ 口；d 2 满足条件l ( 毋) nl ( f 2 ) 西。如果出现这种情况，那 么系统将随机的选择这两条中的其中一条。 系统中的规则按不确定性，最大并行的方式执行。即在某一时间周期内，系 统中的所有的神经元都能使用( 且如果能使用将一定要使用) 一条规则( 发射规 则或遗忘规则) 。 神经元的状态用其离打开状态的最短时间间隔来表示。例如：若某一神经元 在某一时刻正处于打开状态，则当前此神经元的状态为0 ；若某一神经元在某一 时刻正处于关闭状态且下一时刻将处于打开状态，则当前此神经元的状态为1 。 系统中所有神经元中尖峰的个数及其在某一时刻的状态构成了系统的格局。因此 艮= 表示的是神经元f = 1 ，2 m 在某一时刻包含r f 0 个尖 峰，且其将在岛0 时间后打开。我们把初始格局记为= ， 格局g 到c z 的转移记为c 1 辛q 。任意由初始格局开始的格局转移序列称为计算 序列。系统中所有的神经元都处于打开状态，但无规则可用的格局称为终止格局。 可到达终止格局的计算称为可终止计算序列。 3 2 尖峰神经元p 系统的语言 3 2 1 尖峰神经元p 系统作为数字产生器 如果将尖峰神经元p 系统作为数字产生器，可用多种方式表示其计算结果。 8 中山大学学位论文尖峰神经元p 系统 例如，当计算停止时，系统中输出神经元中尖峰的个数可作为计算的结果。或者， 将输出神经元在计算过程中发射到环境中尖峰的个数当作计算结果。 在这里，我们不考虑计算是否能停止，只要求输出神经元有且只有两次将尖 峰发送到环境的动作。输出神经元两次发射的时间间隔定义为系统计算的结果。 我们将系统在这种方式下产生的数字2 ( 兀) 族记做批( ，“厶c d 脚扣r 踟) 。它 表示的是在系统兀中，神经元的个数最多为m ，每个神经元中最多包含七条规则， 每条发射规则最多消耗p 个尖峰，每条遗忘规则最多消耗垡个尖峰。需要说明的 是，当朋，七，p ，目无限制时，则用木代替。s np 系统在任意一个时钟周期，任意神 经元中的尖峰个数均不超过s ，那么该系统被称为有限系统，其语言族记为 n n p 撕越e b c o n sd f o r g q 扫o u n d 3 o 有限语言集，正则语言集和递归可枚举语言集分别记作f w ，艇g ，咫，与 其长度对应的数字集合分别记作：删，咫g ，朋陋。文献 5 】证明了如下定理 成立： 定理3 1 ( i ) f 肼= m 羹w p 朋( ，“跆c d 淞西扣，踟) = 批! - 5 p m ( ，“如，c d 刀s ，加曙) 。 ( i i ) c d 拜嘞扣恸) = 艇，其中良2 ，p 3 ，q 3 。 ( i i i ) 舰肼= c 伽嘞加嘞，6 d “忍以) ，其中七2 ，p 3 ，q 3 ，s 3 。 以上结论对于处于接收模式的s np 系统同样成立【5 1 。 3 2 2 尖峰神经元p 系统作为尖峰链语言产生器 在3 1 节中，文章已经引入了计算序列的概念。对于任意的计算序列( 包括 可终止计算序列和不可终止计算序列) 都有一尖峰链与之相对应。若在某一时刻， 系统中的输出神经元向环境发射了尖峰，则此时输出1 ，反之输出0 。由0 ，1 组 成的字符串即为系统产生的尖峰链。当s np 系统作为尖峰链语言产生器时，仅 考虑系统中的可终止计算序列。我们把系统由初始格局到终止格局所产生的所有 尖峰链的集合定义为s np 系统所产生的语言。其形式化描述如下： n = ( d ，仃1 ，仃z ，妙s 孔，f o ) 表示任意一s np 系统，丫= g 辛c 1 兮号“为 兀的中任意一可终止计算序列，其中，为初始格局，q 一1 辛c f 为丫中的第f 步 计算。二元字母表 0 ，1 】记为b 。6 切( 丫) 表示字符串6 1 6 2 k ，其中6 f ( o ，1 ) 。阢= 1 当且仅当系统n 中的输出神经元在第i 步将尖峰发射到环境当中。c 例订( n ) 表示 中山大学学位论文 尖峰神经元p 系统 系统兀所有可终止状态的集合。那么，系统兀所接收的语言定义为： ( 兀) = ( 6 礼( y ) i y c d m ( n ) ) 我们将工作在这种模式下系统产生的语言族记作l 骶怫。( ，“c d 咒跏肋g g ) ，其 中，聊，七，p ，q 的定义与3 2 1 中相同。若s np 系统为有限系统( 在任意一个时钟 周期，任意神经元中的尖峰个数均不超过s ) ，则将其产生的语言集记为 l f s n p 心u t e b c o n s p f o r 9 0 o 基于以上定义，文献 6 】证明了如下定理： 定理3 2 ( i ) 存在有限集合语言不能被s np 系统产生。但对于任意l 川，l b + ， 有l ( 1 ) 上，彤p l o 训p ，c d 礼& ，厂d 憎o ) 。对于 l = ，x 2 ，) ，有( o i + 3 麓1 1 n ) l 船p 1 蛾，c d n s l ，厂d 憎o ) 。 ( i i ) 有限s np 系统产生的语言族严格包含于 0 ，1 ，上的正则语言集。但 对于任意正则语言z ，y + ，存在s np 系统n 及映射 ：y + - 口+ ，使得 l = 一1 ( l ( n ) ) 。 ( i i i ) l 州p 1 ( 化k 。，住缸，厂d 叼o ) 尺e c 。对于任意字母表 y = ( 口1 ，口2 一，口n ) ，存在映射，1 1 ：u ( 6 ，c ) ) 一口，投影九2 ：u ( 6 ，c ) ) 一y + ，及s np 系统，使得对于任意l y + ，z r r e ，有 l = 2 ( ，i f l ( l ( 兀) ) ) 成立。 3 2 3 尖峰神经元p 系统作为尖峰跟踪语言产生器 本节将介绍另一种s np 系统产生语言的方式。工作在该模式在的s np 系统 不需要输出神经元，但需要一个输入神经元。系统处于初始状态时，在输入神经 元中存在一个为区别于其它尖峰的而被做了标记的特别尖峰。我们将记录特别尖 峰在每个时钟周期内所经过的神经元的标号。如果由于某一规则使用，消耗了该 特别尖峰，那么，由这一规则生成的尖峰将会成为特别尖峰，并进入相应的规则 所在的邻接神经元中。如果规则的使用未消耗特别尖峰，那么，该特别尖峰将继 续留在原神经元内。 我们用字母饥记录特别尖峰所经过的神经元，其中字母轨与任意神经元o f 的 标号相对应。系统n 在这种方式下产生的语言记为孔n ) 。及兀) 所组成的语言族记 】0 中山大学学位论文 尖峰神经元p 系统 作硒! 7 = j 仲概c d 咖嘞) ，其中，朋，七，p ，g 的定义与3 2 1 中的相同。 基于以上定义，文献 7 】证明了如下定理： 定理3 3 ( i ) 存在单集合语言不属于聊( ，w 跆，c d 以s 加r g ) 。 ( i i ) 有限s np 系统产生的跟踪语言严格包含于正则语言集中。但对于 任意正则语言l y ，存在一个有限s np 系统n ，使得l = ，t ( 醒( 7 ( 兀) ) ) ， 其中，j l 为一编码，c 不属于玑z 炉j 2 似z 3 嚣酗加曙3 ) 一艇g 谚。 ( i i i ) 对于任意一元语言l 尺f ，可转化为l = j l ( r ) = ( 蜒) n6 ；的形式， 其中，那只( r u z 屹，c d 7 1 ，厂d r 口3 ) ，其中7 l 为一投影。 1 1 中山大学学位论文尖峰神经元p 系统 第4 章带启动子的异步尖峰神经元p 系统 本章将介绍一种新的计算模型带启动子的异步尖峰神经元p 系统 ( a s n pp 系统) 。它的计算过程与第3 章介绍的s np 系统相似，所不同的是， 新的计算模型是工作的异步的模式下。本章还将证明新的计算模型作为数字产生 器与图灵机有相同的计算能力；作为语言产生器，存在一个映射，使得任意正则 语言集都包含于该系统所产生的语言集的象之中。 4 1 带启动子的异步s np 系统的定义 定义4 1 度数为朋的带启动子的异步尖峰神经元p 系统( a s 御p 系统) 的定 义如下： 兀= ( d ，p ，0 1 ，a 2 ，o m ，妙s 1 o ) 其中： 1 d = ( n ) 为单字母字母表( 口称为尖峰) ； 2 p 为启动启动子的集合，并且口岳p ； 3 仃1 ，为形为d f = e ，s ，甩，r ；) ，1 m 的神经元，其中： a ) 7 t o 为神经元吼在初始状态下尖峰的个数； b ) 函p 为神经元o i 在初始状态下启动子的类型； c ) r 为不带启动子规则的有限集合，有如下两种形式： ( 1 ) e 加c 一口q ，其中c 1 ，q = n 无启动子生成) 或q p ( 有启动子生 成) ，且e 为口的正则表达式： ( 2 ) 口s 一九其中s 1 ； d )尺为带启动子规则的有限集合，有如下两种形式： ( 1 ) e n c 一口口l 鼽c 盯，其中c 1 ，q = 九或q p ，p p ，t 盯 l p r 岛9 d ，仇e 比) ，且e 为口的正则表达式； ( 2 ) 矿_ 九i p c 口r ，其中s 1 ，缸r ( ，l p r e g d ，m p 碱 ； 中山大学学位论文尖峰神经元p 系统 4 夥饥( 1 ，2 ，m ) ( 1 ，2 ，m ) ，对于任意1 f m ，有( f ，) 硭妙趴； 5 o ( 1 ，2 ，m ) 为输出神经元的编号。 由于在第3 章已经介绍了s n p 系统的计算过程，以下内容仅说明a s n pp 系统 与传统s np 系统的不同之处。 首先，传统s np 系统只包含一类规则。在a s n pp 系统中，启动子的引入把 规则分为两类：带启动子的规则和不带启动子的规则。启动子的类型可以有多种， 但在同一神经元中同一类型的启动子只能存在一个。启动子只可以由发射规则产 生。遗忘规则不能生成启动子。启动子一旦生成，它将跟随产生的尖峰沿着突触 到达相应的神经元。启动子最主要的作用是它可以启动某些规则。比如说，在某 个神经元内，尖峰的个数即使满足规则f n c - n q i m 4 r 中正则表达式e 的要求， 但如果没有启动子p 的存在，该规则也不能被使用。当启动子启动了某一规则 ( e 口c _ 口q i p ，c 盯或口s 一九i p ，c 口r ) 时，该启动子将留在规则所在的神经元中( 若 细，= l l 讹) ，到达突触所指向的临近神经元( 若纽，= g d ) ，或者消失( 若缸，= 柳础) 。 启动子对于不带启动子规则没有任何作用。不带启动子规则的使用与第3 章介绍 的规则的使用完全相同。如果启动子到达了某个神经元，但此神经元中没有任何 规则需要该启动子，那么，启动子将会永远留在此神经元中而不起任何作用。 其次，产生规则会生成一个尖峰及一个启动子。我们把形如e a c a q 和 f 口c _ 口q i 弘缸r 的规则定义为产生规则；把形如n s 一九和口s 一九i 鼽c 口r 的规则定义 为遗忘规则。任何产生规则均可以生成一个启动子，但这不是不需的。也就是说， 规则e 口c 一口和规则f 肛c 一口q i p ，c 口r 也是符合定义要求的。 再次，在a s n pp 系统中除去了对于规则n s _ 九中口s 睡l ) 的限制。也就是说， 允许出现在神经元中尖峰的个数既满足发射规则的要求又满足遗忘规则的要求 的情况。 最后，a s n pp 系统与s np 系统最大的不同在于a s n pp 的工作不需要全 局时钟。这使得a s n pp 系统可以在工作的异步的条件下。在传统的s np 系统 中，规则的使用和发射尖峰是两个重要的步骤。神经元在接收到满足规则条件的 尖峰的下一个时钟周期将会使用对应的规则。在经过规则所要求的时间间隔后， 】3 中山大学学位论文尖峰神经元p 系统 该神经元会把生成的尖峰发射到有突触相连的邻近的神经元。在神经元使用规则 和发射尖峰的时问间隔中，神经元处于关闭状态。在a s n pp 系统中，由于没有 全局的时钟，我们定义各神经元使用规则后，可以在任意时间后把所生成的尖峰 及启动子发射到相应的神经元。在神经元使用规则和发射尖峰的时间间隔中，神 经元也处于关闭状态。a s n pp 系统还规定，任一神经元都不能同时接收来自不 同神经元的尖峰与启动子，因为如果某一神经元接收了来自另一神经元的物质并 且该神经元中尖峰的数目满足某规则要求，那么它将立刻使用该规则，随后关闭， 直到生成的尖峰与刺突被发射出去；如果该神经元接收到物质后，没有可以反应 的规则，那么，它将处于打开状态，等待其它尖峰和启动子的到来。 4 2 带启动子的异步s np 系统作为数字产生器 a s n pp 可作为数字产生器。在处于初始状态时，系统中可能会包含一些尖 峰和启动子。然后系统将以异步的方式推进，直到到达终止状态( 即所有的神经 元都处于打开状态，但没有规则使用) 。此时，在输入神经元中的尖峰的个数即 为系统计算的结果。系统最终到达不了终止状态的计算定义为失败的计算。 我们把a s n pp 系统r i 所产生的数字记为心( n ) ，把所有心( n ) 组成的族记为 j 4 s 蹋f ，c d 脚，厂d 憎q ) 。其中，神经元的个数最多为m ，启动子的个数最 多为r ，每个神经元中最多包含七条规则，每条发射规则最多消耗p 个尖峰，每条 遗忘规则最多消耗鼋个尖峰。若朋，七，p ，g 的数值没有限制，则用幸代替。 a s n pp 系统的有强大的计算能力，它作为数字产生器与图灵机是等价的。 定理4 1 ：r e = m 4 s 彤( 化z e 七，c d t t s p ，厂d 叼q ) ，其中r s ，良4 ，p 1 ，q 1 证明：该定理的证明是基于对寄存器的模拟。图4 1 ，图4 2 分别表示的是对寄 存器中加指令( 爿d d ) 模块和减指令( s 凇) 模块的模拟。系统n 中标号为厶的神 经元与寄存器m 中的标号为玉的指令相对应。标号为厂f 的神经元与寄存器m 中的寄 存器相对应，并且神经元r f 中尖峰的个数与寄存器，f 的值相等。标号为c f 的神经元 与寄存器2 呒对应关系，但在系统模拟寄存器各模块工作的过程中有特殊的作用。 在初始状态下，( 1 ) 除神经元如包含一个尖峰外，其它所有的神经元中都没 1 4 中山大学学位论文尖峰神经元p 系统 有尖峰( 但可能存在某些启动子) 。( 2 ) 标号为矗的神经元包含一些启动子：若厶 与加指令( 州如) 对应，则神经元厶中包含启动子d ；若厶与减指令( s 叩) 对应， 则神经元厶中包含启动子6 ；若厶与停止指令( 尼他z ) 对应，则神经元乃中包含启 动子j l 。 加指令易：脚似易助的模拟 如图4 1 所示，神经元z 1 中存在的唯一一个启动子是d 。因此，当神经元z i 收到来自邻接神经元的尖峰后，规则口一口c 1i d ，l e r e 或规则口一口c 2h ，l p r e 将会立刻 被使用。如果系统最终使用的是规则口一口c 1 i d 抛r e ，那么尖峰则会到达如( 因为 尖峰通过神经元c 1 时，规则口_ 口k m 硪将被使用，而尖峰通过神经元c 2 时，规则 口一入l c ，肌e c 将被使用) ；反之如果系统最终使用的是规则口一口吃k ，l 盯e ，那么 尖峰则会到达如。神经元，也将会收到来自神经元z 1 启动子c 1 或者c 2 ，但是它们将 永远停留在那里但不起任何作用。 图4 1 仰d 指令模块的模拟 中山大学学位论文尖峰神经元p 系统 减指令易：岱咄似易功的模拟 如图4 2 所示，神经元z 1 存在的唯一一个启动子是6 。因此，只有规则 口_ 盯k ，l e r p 可以被使用。神经元z 1 发射出尖峰口和启动子，后，它们将会到达神经 元，在神经元，中，若到达的尖峰是此神经元中唯一存在的尖峰，则规则 n n c 2i r m p i c 将被使用，产生一个尖峰口及启动子c 2 ，并且神经元，中尖峰的个数 保持不变( 保持为o ) ；反之，若到达的尖峰不是此神经元中唯一存在的尖峰， 则规则n 口+ 肛2 一口qi r 肌班将被使用，产生一个尖峰口及启动子c 1 ，并且神经元r ， 中尖峰的个数比原先减少1 。如果最终产生的是启动子白，那么尖峰将最终到达 如，反之，如果最终产生的是启动子c 2 ，那么尖峰将最终到达z 3 。 计算的终止 口_ 口l 2 ，枷 口_ a l c l 础 l 一 上 r、 d 1 6 i 口_ 口c 1l 胁 口_ 口c 2l d 概 口_ 口，k 概 口_ ak 胁 图4 2 s 指令模块的模拟 中山大学学位论文尖峰神经元p 系统 当神经元纸( 其中包含启动子 ) 得到一个尖峰后，规则n _ 入i _ 1 m m 将会被 使用，因为该神经元中除 之外，不含其它的启动子。使用此规则后，将不再有 尖峰在神经元厶中，也就意味着计算的终止。此时，神经元，1 中尖峰的个数即为 计算的结果。由于该神经元与寄存器m 中的寄存器1 相对应，因此( m ) ( n ) 。 于是有j 尺f m 4 s j 彤( 九以鼠，c 0 7 l 昂，厂d 咽q ) 。 从而，最终证得r f = 4 s 彤( 化f ，c d n 却，厂d 憎q ) 。 口 4 3 带启动子的异步s np 系统作为语言产生器 a s n pp 系统通过如下的方式产生语言： 在系统中我们标记一个特别尖峰。 通过记录该特别尖峰在系统中运动所经过的神经元的标号，最终得到系统所产生 的语言。系统的计算是成功的当且仅当系统最终到达了终止格局或者特殊神经元 最终消失。 由于系统中没有同步时钟，因此，无论特别尖峰在某个神经元中停留多长时 间，都认为只产生了一个字符。这一点和传统的s np 系统是不同的。根据a s n p p 系统的定义，所有神经元都没有指向自身的突触，因此，a s n pp 系统不会产 生包含同一字符连续出现的字符串。在这里，输出神经元f o 可以省略。 我们把a s n pp 系统兀由上述方式产生的所有字符串记为瓦( n ) ，把所有( 兀) 组成的族记为丁诅鳓f ( ，z ，c d 7 l ，厂d 憎口) 。其中，m ，巧毛p ，g 的定义与5 4 2 节 中的相同。 以下我们将证明正则语言集包含于a s n pp 系统所产生的语言的映射中。 定理4 2 ：对于任意正则语言l y ，都存在一个a s n pp 系统兀及映射j l ，使得 l j l ( r ( 兀) ) ，其中7 ( ) 孤s 耳( 似f p 。，c d 街1 ，厂。叼1 ) 。 证明：设正则文法g = ( ，n a l ，p ) ，其中= 似1 ，a 2 ，a m ) ，矿= ( 6 1 ，6 2 一，k ) 。 根据文法g 可通过如下方法构造另一文法g ：首先令g 7 = ( ，y 0 a o ，p 7 ) ，其中 1 7 中山大学学位论文尖峰神经元p 系统 ，_ ，y ，_ yu ，p ，一p 。若集合中存在形如 -