膜计算-谭立伟

膜计算android与算法俱乐部谭立伟参考文献陈海珠.膜计算应用研究.重庆大学博士学位论文,2011.4概述膜计算(MembraneComputing，也称为P系统)是自然计算的一个新分支，其目的是从活细胞中以及组织、器官或其他结构的细胞之间相互协作的方式中获得新的计算思想、设计新的计算模型。P系统不仅为计算机科学引入了新的分布式并行信息处理方法和技术，而且为生物系统的建模和仿真提供了新工具，是当前非常活跃的一个研究领域，预计在新一代计算系统、信息处理系统的技术开发方面将起关键作用。关于膜计算的研究工作可归为三类：理论研究、应用研究和软、硬件实现研究。膜计算的理论研究主要集中于各种计算模型的建立及其计算能力(ComputationPower)的分析；膜计算的应用研究主要是利用P系统的特点和各种模型求解生物学、计算机科学、语言学、社会学等方面的实际问题；而膜计算的软硬件实现研究则侧重于在现有计算机上用程序实现或开发新的处理器实现有关的膜计算模型或求解有关问题。尽管P系统还处于理论研究阶段，但它所具有的一些性质如并行性、非确定性等已经引起了越来越多学者的研究和关注。随着研究的深入，由原始模型衍生出了许多不同的膜计算模型，主要有：类细胞P系统(Cell-likePSystems)、类组织P系统(Tissue-likePSystems)类神经P系统(Neural-likePSystems)它们分别是从细胞、组织以及神经系统中抽象而来的计算模型。形式语言基础对于字母表V，V*(V的闭包)表示V上所有有限字符串的集合。空字符串用λ表示。V上的所有非空有限字符串用V+(V的正闭包)表示，即V+=V*−{λ}V*的任意一个子集称为V上的一个语言如果V={a}（这时称V为单字母表），则{a}*，{a}+分别简记为a*，a+字母表V上的正则表达式(正规式)定义如下：①λ和a∈V都是正则表达式；②如果E1，E2是V上的正则表达式，则E1E2,E1∪E2，E1+都是V上的正则表达式；③除①、②之外，V上不再有其他正则表达式。正则表达式E对应于一个语言L(E)，L(E)按如下方式定义：①L(λ)={λ}以及对每个a∈V，有L(a)={a}；②对V上的任意表达式E1，E2，有L(E1∪E2)=L(E1)∪L(E2)L(E1E2)=L(E1)L(E2)L(E1+)=L(E1)+在不引起歧义的前提下，正则表达式中的某些括号可以省略。另外，对于任意正则表达式E，把E+∪{λ}简记为E*。类细胞P系统类细胞P系统是第一个被提出来的P系统。类细胞P系统将生物膜内的化学反应与膜间的物质流动抽象为计算过程：生物膜内的化学反应就是通常理解的计算过程，而物质在不同膜之间的流动则对应于通常意义计算系统中的消息传递，细胞或细胞器成为计算单元。类细胞P系统结构的示意图最外边的膜称为皮肤膜(skinmembrane)，它将本系统与外在环境分开。如果一个膜的内部不存在其他膜，就称这个膜为基本膜(elementalmembrane)，否则称为非基本膜(non-elementalmembrane)。每一个膜定义了一个区域：对于基本膜，这个区域就是它所包含的空间；对于非基本膜，区域是指这个膜和它直接包含的其他膜之间的空间。膜结构的描述通常有两种方式:树形结构-膜的层次结构特征适合于用树结构来描述：皮肤做为根节点，基本膜做为叶节点。广义表用嵌套结构即是用字符串来表示膜结构。当i#膜为基本膜时，表示为：[i]i；当k#膜包含在i#膜内部时，表示为[i[k]k]i。一对括号[]表示一个膜，括号的下标为膜的标号。例如，上图的膜结构可表示为：[1[2]2[3]3[4[5]5[6[8]8[9]9]6

[7]7]4]1。在膜结构的描述中，同一层次的膜的排列顺序是任意的。故对同一个P系统，其描述形式不是唯一的。在生物膜内存在多种物质，如离子、小分子、微分子等。每种物质通常不止一个，并且是无序的。在P系统中使用小写字母来表示这些物质，这样膜中含有的物质就可以用多重集表示。所谓多重集是指允许有相同元素的集合。例如，A={a,a,b,c,c,c}是多重集，记为{a2,b,c3}或a2bc3。多重集表示是无序的，即a2bc3与bc3a2是同一个多重集。膜作为细胞的边界，细胞内包含的物质是膜计算的对象，物质的反应以及膜之间物质的流动是膜计算的过程，这一过程中膜内物质及其数量发生改变，不同的改变过程对应着不同的进化规则。P系统中，往往存在多种对象和多个进化规则，规则执行的原则是:不确定性

-当有n个规则需要执行m个，具体是哪m个是随机的最大并行性-每次执行所有可执行的规则都必须执行且同时执行。给定一个P系统，即给定了一个膜结构，并且各个膜里都包含有相应的字符串和进化规则，这个称为P系统的初始格局。从初始格局开始，P系统的各个膜不确定、最大并行地使用规则，系统每运行一步(也称为一个计算步)，当前格局就会做相应的改变进入一个新格局。经过若干计算步，形成一系列的格局。当没有规则可以执行，系统进入停机状态。整个格局序列被称为P系统的一次计算，被送到环境或指定膜中的对象即是计算的结果。若P系统的规则一直执行，无法进入停机状态，则计算无效，也就没有计算结果。转移P系统、协同P系统、活性膜P系统是类细胞P系统的三种基本模型，它们从不同角度模拟了细胞内物质对象的变化过程，故采用不同的规则。其中，转移P系统是膜计算应用中最常使用的一种计算模型，其形式化定义为：O是非空有限的字符集，每个符号表示膜结构中的一种对象(也即物质)μ是膜结构，度为m，每个膜都有相应的标号，H={1,2,,m}为∏的标号集合；wi

(i=1...m)为i#膜中对象的集合，用多重集表示，wi=λ表示i#膜内没有任何对象；Ri为i#膜内的进化规则(定义见下页)i0是膜结构的输出区域，该区域最后保存计算结果。进化规则形式为u→v或u→vδ，u∈O+，v∈(O×Tar)*,Tar={here,in,out}，Tar表示生成物v的去向：here表示v留在i#膜内；inj表示v被送至j#膜内，j#膜是i#膜的子膜；out表示v被送至i#膜外成为其父膜中的对象。δ是溶解操作，它溶解对象u所在的i#膜，其所在膜内所有的对象都被释放到其父膜内，并且定义在i#膜内的规则也会跟着消失，δ操作不能应用于皮肤膜。在细胞的进化中，除了细胞内物质种类、数量变化外，还会发生细胞分裂等细胞繁殖活动。活性膜P系统即是抽象这一细胞活动而得到的计算模型。此类P系统将膜也作为规则处理对象，其规则包括膜的溶解、膜分裂、膜创建、膜分离和膜合并等。采用活性膜P系统进行计算时，膜结构随着膜操作规则的执行而发生着变化。活性膜P系统的一般形式与转移P系统的相同，区别在于规则不同。活性膜P系统使用的规则为：对象进化规则：当h#膜所带电荷为e时(当e为0时表示h#膜没有极性，此时可不必写出，下同)，其中的对象a可进化为v(v为对象集合)。通信规则：当h#膜所带电荷为e1时，膜外对象a可进入h#膜且进化为对象b；当h#膜所带电荷为e2时，膜内对象a可移出h#膜之外(进入h#膜的上一层膜)且进化为对象b。(注意，原文有误)Π中规则的执行仍然采用不确定、最大并行原则。对②～④类型的规则，在同一时刻每个膜中只能使用一种，而规则①可与②～④同时使用。举例以下图的转移P系统为例来解释P系统的计算过程。该系统描述为：计算过程为：（1）仅有3#膜的规则能被执行，显然，在同一时刻，{a→ab,f→ff}与{a→bδ,f→ff}仅有其中一组能被执行。现假设{a→ab,f→ff}执行n次后再执行一次{a→bδ,f→ff}。因a→bδ的执行，使3#膜被溶解，多重集(n≥0)被带到2#膜中。(注意，原文有误)(2)在2#膜中，分两种情况：1)n=0，多重集为bcf2。{b→d,ff→f}或{b→d,cf→cdδ}能先执行。a.先执行{b→d,ff→f}，然后只有{d→de,cf→cdδ}能被执行。此时，2#膜被溶解，多重集cd2e被送到1#膜中。b.先执行{b→d,cf→cdδ}，2#膜被溶解，多重集cd2f被送到1#膜中。2)n>0，多重集为。a.先执行{b→d,ff→f}，得到多重集。这时再执行规则集{d→de,ff→f}，得到，重复执行此规则集k(k<n)次后，得到：当k=n时，得多重集，这时可执行的规则集为{d→de,cf→cdδ}，执行之，2#膜溶解，多重集被送到1#膜中；当k≠n时，执行规则集{d→de,ff→f,cf→cdδ}，2#膜溶解，被送到1#膜中。b.先执