通用进化处理器网络的建设与图灵机模拟研究

理论计算机科学电子笔记135（2006）95-105www.elsevier.com/locate/entcs一种通用的可接受进化处理器Florin Manea1布加勒斯特大学数学与计算机科学学院Str. Academiei 14，70109，布加勒斯特，罗马尼亚CarlosMart 'ın-Vide2数学语言学研究小组，罗维拉伊维利大学PcaImperialTa`rraco1，43005Taragona，Spain维克托·米特拉纳2布加勒斯特大学数学与计算机科学学院Str. Academiei 14，70109，布加勒斯特，罗马尼亚和数学语言学研究小组，罗维拉伊维利大学PcaImperialTa`rraco1，43005Taragona，Spain摘要我们提出了一个接受混合网络的进化处理器（AHNEP）的行为作为一个通用的设备在所有这些设备的类的建设。我们首先构造一个可以模拟任何AHNEP的图灵机，然后构造一个模拟图灵机的AHNEP我们认为，这种方法可以应用到其他生物启发的计算模型，计算完成。保留字： 进化处理器网络，图灵机，普适性1Email：flmanea@ f unin f. cs. 联合国教科文组织Ro2Email：{carlos. martin，vmi}@urv. net1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.09.02496F. Manea等人/理论计算机科学电子笔记135（2006）951引言本文讨论的研究路线位于植根于分子生物学的广泛计算模型中[13]。简单介绍一下引入这里讨论的模型一个相当著名的并行和分布式符号处理的体系结构，与连接机[9]以及逻辑流范例[7]相关，由几个处理器组成，每个处理器被放置在虚拟完整图的一个节点中，它们能够处理与相应节点相关联的数据每个节点处理器根据一些预定义的规则对本地数据进行操作，然后本地数据成为可以遵循给定协议在网络中导航的移动代理只有能够通过过滤过程的数据才能被传送到其他处理器。该过滤过程可能需要满足由发送处理器、接收处理器或两者施加的某些条件根据某些策略，所有节点同时发送它们的数据，并且接收节点也同时处理所有到达的消息，参见例如，[8、9]。从数据可以以词的形式给出的前提出发，Csuhaj-Varju′Salomaa在[5]中引入了一个paral-lel语言处理器的概念，目的是从形式语法和语言的角度研究这个概念在[1]中，这一概念受到了细胞生物学的启发。网络节点上的每个处理器都是一个非常简单的处理器，一个进化处理器。这不是一个真实存在的物体，而是一个数学概念。进化处理器是指能够执行非常简单的操作的处理器，即模拟DNA序列中的点突变（一对核苷酸的插入、缺失或取代）的形式语言理论操作更一般地，每个节点可以被视为具有编码在DNA序列中的遗传信息的细胞，其可以通过局部进化事件（即点突变）进化每个节点都专门用于这些进化操作中的一个此外，每个节点中的数据以多组单词的形式组织（每个单词以任意数量的副本出现），并且所有副本都被并行处理，以便所有可能发生的事件从生物学的角度来看，不能期望任何生物有机体的组分按顺序进化单元状态的变化是通过重写规则来建模的，就像在形式语法中一样。单元状态变化的并行性质通过根据所应用的规则并行执行符号重写来建模因此，进化处理器的混合网络可能被视为生物启发的计算模型。显然，这里描述的计算过程并不完全是一个F. Manea等人/理论计算机科学电子笔记135（2006）9597达尔文意义上的进化过程但是我们已经考虑过的重写操作可以被解释为突变，而过滤过程可以被看作是选择过程。虽然没有明确说明，但有人断言，基因之间的进化和功能关系可以通过仅考虑局部突变来捕获[15]。此外，我们在这里并不关心可能的生物实施，尽管这是一个非常重要的问题。我们在[1]中介绍的机制在一系列子程序[2，12]中被进一步考虑作为语言生成设备，并研究了它们另一方面，这个模型在[11]中被认为是一个接受设备，其中获得了NP的新特征，以及[12，10]中的问题求解器，其中一些NP完全问题在线性时间内用多项式有界的资源求解上述模型，除了数学的动机，也可能有一个生物学的。细胞总是形成组织和器官，这些组织和器官直接或通过共同的环境相互作用。在本文中，我们提出了一个接受的混合网络的进化处理器的行为作为一个通用的设备在所有这些设备的类的建设我们首先构造一个可以模拟任何AHNEP的图灵机，然后构造一个模拟图灵机的AHNEP。图灵机的构造在这里介绍，而AHNEP的构造读者可以参考[11]。这一结果与AHNEP是一个确定性和计算完整的设备，灵感来自细胞生物学，并适合用作问题求解器（见[10]，其中讨论了使用WWW的AHNEP的可能实现）的事实一起，表明有可能构建一种2基本定义首先，我们总结了整个论文中使用的概念字母表是一组有限的、非空的符号。一个有限集合A的基数是写卡（A）。来自字母表V的任何符号序列称为V上的字（串）。V上所有词的集合记为V，空字用ε表示。 一个单词x的长度表示为：|X|while alph（x）表示最小字母表W，使得x∈W<$。我们说规则a→b，其中a，b∈V<${ε}是替换规则，如果a和b不是ε;如果a ε和b=ε，则它是删除规则;它是插入规则如果a=ε且b/=ε。字母表V上的所有替换、删除和插入规则的集合分别用SubV、DelV和InsV表示。对于字母表V和a的两个不相交的非空子集P和F，98F. Manea等人/理论计算机科学电子笔记135（2006）95在V上，我们定义谓词：•（1）（w;P，F）•（2）（w;P，F）•（3）（w;P，F）• （4）（w; P，F）V上的进化处理器是元组（M，PI，FI，PO，FO），其中：– M是字母表V上的一组替换、删除或插入规则。形式：（MSubV）或（MDelV）或（MInsV）。集合M表示处理器的进化规则的集合可以看到，A处理器只– PI、FI、FIV是处理器的输入允许/禁止上下文，而PO、FO、FIV是处理器的输出允许/禁止上下文。非正式地说，允许的输入/输出上下文是当字符串进入/离开处理器时，禁止上下文是应该出现在字符串中的符号的集合，而禁止上下文是为了进入/离开处理器而不应该出现在字符串我们用EPV表示V上的进化处理器的集合。进化处理器的可接受混合网络（简称AHNEP）是一个7元组Γ =（V，U，G，N，α，β，xI，xO），其中：• V和U分别是输入和网络字母，V<$U。• G=（XG，EG）是一个无向图，称为网络的底层图。在本文中，我们考虑完全AHNEPs，即。AHNEPs有一个完整的底层图表示为Kn，其中n是顶点的数量。• N：XG−→EPU是一个映射，它将每个节点x∈XG与进化处理器N（x）=（Mx，PIx，FIx，POx，FOx）相关联。• α：XG−→{x，l，r};α（x）g表示n个x的规则对该节点中存在的非正式地说，这表明处理器的进化规则是否应用于字符串的最左端，对于α = r，α = l，在字符串的最右端，或者对于α = r，在字符串的任何位置。• β：XG−→{（1），（2），（3），（4）}定义节点的输入/输出滤波器的类型更准确地说，对于每个节点x∈XG，定义以下滤波器：输入滤波器：ρx（·）=ρβ（x）（·;PIx， FIx），F. Manea等人/理论计算机科学电子笔记135（2006）9599GX我i−1输出滤波器：τx（·）=τβ（x）（·;POx， FOx）。即ρx（w）（resp. τx）指示单词w是否可以通过输入（分别输出）x的滤波器。更一般地，ρx（L）（resp. τx（L））是L的可以通过输入（分别为输出）x的滤波器。• xI和xO∈XG分别是AHNEP的输入节点和输出节点上面的AHNEP Γ的一种配置是映射C：X −→2V其将一组单词与图的每个节点相A配置可以被理解为在给定时刻存在于任何节点中的词的集合。一个配置可以通过进化步骤或通信步骤来改变。当通过进化步骤改变时，配置C的每个组件C（x）根据与节点x相关联的进化规则集Mx以及应用这些规则α（x）。 形式上，我们说配置CJ由下式获得：从构型C进化而来的一步，记作C=<$CJ，i <$CJ（x）= Mα（x）（C（x）），对所有x∈ XG.当通过通信步长改变时，每个节点处理器x∈XG发送它所拥有的每个单词的一个副本，该副本能够通过x的输出过滤器，发送到连接到x的所有节点处理器，并接收由连接到x的任何节点处理器发送的所有字，只要它们可以通过其输入滤波器。形式上，我们说配置CJ是在一次通信中获得的从配置C开始的步骤，记作CCJ，iCJ（x）=（C（x）−τx（C（x））<$（τy（C（y））<$ρx（C（y）对于所有x∈ XG。{x，y}∈EG请注意，离开节点的单词将从该节点中删除如果他们不能通过任何节点的输入过滤器，它们就会丢失。设Γ是一个AHNEP，是一个配置序列C（w），C（w），C（w），. . ，其中C（w）是初始0 1 2 0定义为C（w）（xI）=w和C（w）（x）= n的Γ的构形，对所有x∈XG，x/=xI，C（w）=C（w）0C（w）0► C（w），对于所有i≥0。 在前一次的Def2i2i+12i+12i+2对于初始化，每个配置C（w）由配置C（w）唯一确定。否则，AHNEP中的每个计算都是确定性的。如果以下两个条件之一成立，则上述计算立即停止(i) 存在一种配置，其中存在于输出节点xO中的单词集合是非空的。在这种情况下，计算被称为接受计算。(ii) 存在两个连续的相同配置。100F. Manea等人/理论计算机科学电子笔记135（2006）95在上述情况下，计算被称为有限的。接受的语言是L（Γ）={w∈V<$|在W上的Γ的计算是可接受的}。3编码完整AHNEPs在本节中，我们将描述一种使用固定字母表对任意AHNEP进行编码的方法A={$，#，r，l，n，（1），（2），（3），（4），0，1，2，·，→}。设Γ =（V，U，Kn，N，α，β，xI，xO）是AHNEP，其中- V ={a1，a2，.，am}，- U = { a 1，a 2，.，ap}，p≥ m，-K n的节点是x1，x2，. ，xn，其中x1= x1且x2= x0。我们对U的每个符号ai进行编码，并将此编码表示为ai>，如下所示：<⎧10i， 1≤i≤m=0 20i，m +1≤i≤p给定w，如上所述的U上的一个词，我们以下面的方式定义它的编码<ε >= 1，= < b2>. ，k≥ 1，bi∈U，1 ≤i≤k. 设L是一个有限语言，L ={w1，. ，wk}。我们用=···.. ··。 空语言<由>=·编码。作为上述的直接结果，我们描述了进化规则是如何编码的：– 代换：a→b，a，b∈V编码为→;– 插入：ε→a，a∈V编码为1 →;– 删除：a→ε编码为→1。我们用表示进化规则r的编码。 一组演化规则：R ={r1，.，r，m}被编码：=···.. ··对于每个节点x，我们设置=######，且 β（x）#。我们现在描述Γ的编码方式这是：< r>= $$$$. $xn>，其中Kn>=2n。< w >，则对于某些AHNEP Γ和w，以下成立：<• 当且仅当r在输入w上停止时，rU在输入r> w>上停止。<• w>被rU接受当且仅当w被r接受这个构造的第一步是定义一个图灵机，它的行为如下一个定理所述。定理4.1存在一个图灵机TU，输入字母表A，在任何输入Γ> w>上满足下列条件，其中 Γ是任意AHNEP，w是输入字母表Γ上的一个字：<• 当且仅当Γ在输入w上停止时，TU在输入<Γ>上停止。• <<当且仅当w被Γ接受时，Γ > w >被TU接受。证明：我们描述了获得TU 令TJ成为一个四带图灵机机器，磁带上标有W、X、Y、Z。这台机器实现如下：初始化在磁带W上找到输入字：Γ> w>。< 设Γ =（V，U，Kn，N，α，β，xI，xO），Kn的结点为x1，x2，.，xn，其中x1= x1且x2= x0。我们把图Kn的编码复制到磁带X上。这意味着在磁带X上，我们将有n次符号2的这可以通过复制第一次和第二次出现之间的部分来完成。<$.该磁带上的每个符号2将用于跟踪在给定时刻处理的节点。在带Y上，我们构造了Γ的初始这是通过以下方式进行的– 首先，我们在磁带Y上写n+1个符号，如果在磁带X上有n个符号1，– 然后，在磁带Y上出现的前两次$之间，我们从输入磁带中复制，并将其放置在两个项目符号之间，– 最后，在所有其他出现的符号之间放置一个项目符号$.总而言之，磁带Y的内容将是：$··$·$·. ·$·$。我们的战略如下：102F. Manea等人/理论计算机科学电子笔记135（2006）951. 第i个节点的配置的编码将被存储在磁带Y上符号$的第i次和第（i+ 1）次出现之间。2. 磁带Y和Z，后者最初包含n+ 1个符号$，将用于模拟进化和通信步骤。3. 进化和交流阶段交替地一个接一个地运行，两者都在接受阶段之前。进化我们假设在磁带Y上我们有一个Γ的构形的编码（假设在第二阶段之后成立）。首先，我们将把Z带进$·$·$·. ·$·$并在磁带X上标记最左边未标记的符号2。假设在标记了这样一个符号之后，在磁带上标记的符号X。我们将磁带W的磁头放在磁带上的第（k+1）个符号$上，将磁带Y和Z的磁头放在第k个符号$上。不难看出，磁带W的头被放置在节点xk的编码开始处，磁带Y的头被放置在配置C（xk）的编码开始处。现在我们将当前状态α（xk）存储起来，并从磁带W中读取xk的第一个进化规则的编码。让我们假设这个编码是单词sl→sr，sl;如果sl/= 1，那么我们逐个考虑C（xk）编码中的所有单词，并且对于它们中的每一个，我们如下进行(I) 如果α（xk）= 1，那么寻找sl的第一次出现。(II) 如果没有发现这种情况，则在磁带Z上插入单词，后面跟着一个项目符号。(III) 如果发现了sl的出现，则继续执行以下任务之一：(i) 将SL替换为SR，假设SR= 1，(ii) 删除sl，假设sr= 1并且所获得的字不为空，(iii) 将sl替换为1，否则为。(IV) 在磁带Z上插入在（III）中获得的字样，然后加上一个项目符号。寻找下一次出现的sl在原来的单词和执行（III），直到所有出现的sl被发现。(V) 如果α（xk）=l，则检查单词是否以sl开头。如果不是这种情况，则执行（II），否则执行（III），并在磁带Z上插入获得的单词，后跟一个项目符号。(VI) 如果α（xk）=r，则检查单词是否以sl结尾。如果不是这种情况，则执行（II），否则执行（III），并在磁带Z上插入获得的单词，后跟一个项目符号。F. Manea等人/理论计算机科学电子笔记135（2006）95103如果sl= 1，那么我们逐个考虑C（xk）编码中的所有字，并且对于它们中的每一个，我们如下进行(I) 如果α（xk）= 1，那么寻找第一次出现的1或2。(II) 在此出现之前插入sr，并在磁带Z上插入获得的单词，后跟项目符号。(III) 重复（II）对原单词中出现的所有1和2(IV) 在原单词的末尾附加sr，然后在磁带Z上插入新单词，后面跟着项目符号。(V) 如果α（xk）=l，则在第一次出现1或2之前插入sr，并在磁带Z上插入获得的单词，然后插入一个项目符号。(VI) 如果α（xk）=r，则在单词的末尾附加sr，并在磁带Z上插入新单词，后跟一个项目符号。我们对xk的所有演化规则重复上述过程。然后，我们在磁带X上标记第（k+1）个符号2，并在该磁带上的第（k+2）个符号$上移动磁带W的磁头，在第（k+1）个符号$上移动磁带Y和Z的磁头。对于图灵机的新配置，我们继续上面描述的过程当在磁带X上没有更多的符号要标记时，我们取消标记所有的符号，并且只保留磁带Z上任何符号对$之间存在的相同字的一个副本此时，在磁带Z上，我们发现了在进化步骤Γ中从磁带Y上编码的构型中获得的构型的编码。现在我们进入沟通阶段。通信首先，我们将磁带Z转换为$·$·$·. ·$·$并在磁带X上标记最左边未标记的符号2。假设在标记这样的符号之后，在磁带X上正好有k个标记的符号。我们把磁带的开头W在该磁带上的第（k+1）个符号$上，以及磁带Y和Z的磁头在第k个符号$上。在当前状态下，我们记住滤波器的使用方式（编码在的最后一个符号中），并读取定义xk的输出滤波器的集合。由于滤波器由基于有限符号集的随机上下文条件定义，因此很容易检查磁带Z上的C（xk）中的一个字是否验证了输出滤波器施加的条件所有不能通过输出过滤器的单词都被标记在磁带Z上，并在磁带Y上插入一个项目符号。在对C（xk）的所有字执行此操作之后，我们重复在磁带X上标记新符号的过程。104F. Manea等人/理论计算机科学电子笔记135（2006）95UU当在磁带X上没有符号要标记时，我们恢复磁带X的原始内容。此时，在磁带Z上放置了n个单词，这些单词代表在最后一个进化步骤之后的配置编码，这些集合中的一些单词被标记。每个子词中的标记子词是不能离开节点x的单词的精确标记编码。此外，磁带Y包含n个字，这些字对不能离开节点的字集进行编码。同样，我们在磁带X上标记最左边的未标记符号2;假设在标记这样一个符号之后，在磁带X上正好有k个标记符号。我们将磁带W的磁头放在该磁带的第（k+ 1）个符号$上，将磁带Y的磁头放在第k个符号$上，将磁带Z的磁头放在第一个符号上$.现在我们来读定义xk的输入滤波器的集合。然后我们检查是否未标记的单词从C（x1），C（x2），.，C（xn）满足输入滤波器xk所施加的条件。所有这些词都插入，然后是一个子弹符号，在磁带Y上。当过程完成时，我们继续在磁带X上标记另一个符号，并在磁带Z上恢复过程。当磁带X上没有符号可以标记时，恢复磁带的初始内容，只保留磁带Y上任何符号对$之间的相同字的一个副本，并取消磁带Z上所有符号的标记。此时，在磁带Y上找到了在通信步骤Γ中从磁带Z上编码的配置中获得的配置的编码。验收如果在进化或通信步骤之后与xO相关的配置不是空的，则计算停止，我们的机器接受输入的单词。否则，如果在进化或交流步骤之前，来自磁带Y和Z的单词是相同的，计算也会停止，但输入的单词不会被接受。显然，上述所有操作都可以通过以下方式正式实现：图灵机我们得到TJ实现所需的行为。从一个经典的结果，它遵循存在一个1-tape图灵机，TU，和TJ的行为一样。这就结束了定理的证明Q构造泛AHNEP的最后一步是基于[11]中证明的以下定理：定理4.2 [11]对于任何识别语言L的图灵机M，存在接受相同语言L的AHNEP Γ。此外，从上述定理的证明可以得出，AHNEP Γ在与M完全相同的输入词上停止。因此，我们可以F. Manea等人/理论计算机科学电子笔记135（2006）95105构造一个AHNEP ΓU，它实现了与TU相同的行为，T U是通用的AHNEP。因此，我们证明：定理4.3存在输入字母表为A的AHNEPΓU，在任何输入 Γ> w>上满足以下条件，其中 Γ是任意AHNEP，w是输入字母表Γ上的字：<• 当且仅当r在输入w上停止时，r U在输入上停止。• 被r U接受当且仅当w被r接受。引用[1] 卡斯特拉诺斯角陈文，用进化处理器网络解决NP完全问题，2001年（北京）计算机科学出版社。Prieto，eds.），LNCS 2084（2001），621-628.[2] J. 卡斯特拉诺斯角马丁-维德Mitrana，J.Sempere，进化处理器网络Acta Informatica39（2003），517-529.[3] J. Castellanos，P. Leupold，V. Mitrana，进化处理器混合网络的描述和计算复杂性方面。理论计算。Sci. 330，2（2005），205-220.[4] E. 你好，J 。 去你的，J 。 Kelemen ，G. 当然 了 ， 我 们 是 系 统 的 。 1993 年，Gord onandBreach。[5] E. Csuh aj-Var ju'，A. 在这一点上，我们有两个或两个以上的相关生产者。 F语言中的新概念（G. P.这是罗马，这是罗马。），LNCS1218，SpringerVerlag，1997，299-318。[6] E. Csuh aj-Var ju'，A. 此外，我们还将继续努力，使我们的网络系统更加安全。 Proc。 InternationlConference Words ， Languages &Combinatorics III （ M. 伊 藤 ， T.Imaoka ，eds.），世界科学，新加坡，2003年，134 - 150。[7] L.埃里科角Jesshope，Towards a New Architecture for Symbolic Processing。 1994年机器人人工智能与信息控制系统Plander，ed.），《世界科学》，新加坡，1994年，31 - 40。[8] S. E. Fahlman，G. E. Hinton，T. J. Seijnowski，人工智能的大规模并行架构：NETL，THISTLE和Boltzmann机器。Proc.AAAI National Conf. on AI，William Kaufman，Los Altos，1983，109- 113.[9] W. D.希利斯，《连接机器》，麻省理工学院出版社，剑桥，1985年。[10] F.马内阿角陈文辉，“利用网际网路求解3CNF-SAT与HPP之线性时间关系”，微控制器2004，第3354期，第269[11] M. Margenstern，V. Mitrana，M. Perez-Jimenez，Accepting hybrid networks of evolutionaryprocessors，Pre-proc. DNA 10，2004，107[12] C. Martin-Vide，V. Mitrana，M. Perez-Jimenez，F. Sancho-Caparrini，进化处理器的混合网络，Proc. 的GECCO 2003，LNCS 2723（2003），401 - 412。[13] G. Paun，G. Rozenberg、A. 这是一个洛马，DNAOM把我的。《新复合材料》，柏林，1998年。[14] G. 我的朋友，我的朋友。 一个不是roduction。 SpringerVerlag，Berlin，2002.[15] D. Sanko，G. Leduc，N.安托万湾帕昆湾F.朗河Cedergren，基因顺序比较系统发育推断：线粒体基因组的进化。Proc. Natl. Acad. Sci. USA，89（1992），6575 - 6579.