宋勃升， 李艷艷， 曾湘祥

(湖南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410082)

在生物啟發(fā)式計(jì)算或者自然計(jì)算的領(lǐng)域內(nèi)，存在一個(gè)快速發(fā)展的分支：膜計(jì)算，由歐洲科學(xué)院院士P?un[1]于1998 年在芬蘭圖爾庫(kù)計(jì)算機(jī)科學(xué)中心訪學(xué)時(shí)首次提出，它是從活細(xì)胞的組織和器官的結(jié)構(gòu)以及功能中抽象出來(lái)的. 膜系統(tǒng)(又稱為P系統(tǒng))是膜計(jì)算研究中計(jì)算模型的統(tǒng)稱，它們是分布式和并行計(jì)算設(shè)備. 根據(jù)活細(xì)胞內(nèi)部的真實(shí)膜結(jié)構(gòu)，許多類型的膜系統(tǒng)已經(jīng)被提出[2-5]，主要有兩類P系統(tǒng)：細(xì)胞型P系統(tǒng)[1,4](一個(gè)細(xì)胞中的膜是以一個(gè)層次結(jié)構(gòu)排列)和組織型P系統(tǒng)[4,6]，或者神經(jīng)型P系統(tǒng)[7](如一個(gè)組織或一個(gè)神經(jīng)網(wǎng)絡(luò)置于任意圖節(jié)點(diǎn)中的膜結(jié)構(gòu)). 根據(jù)生物活細(xì)胞具有不同的生物特征，研究者們又提出了許多新型的膜系統(tǒng)，例如，帶催化劑的膜系統(tǒng)[8]、帶促進(jìn)劑/抑制劑的膜系統(tǒng)[9]和剪切膜系統(tǒng)[10]等.

膜計(jì)算的研究課題主要聚焦在理論分析和現(xiàn)實(shí)生活問題的應(yīng)用上. 一方面，隨著各種P系統(tǒng)的引入，許多不同種類P系統(tǒng)的計(jì)算能力以及計(jì)算復(fù)雜性已經(jīng)被深入地研究[11-15]. 結(jié)合計(jì)算機(jī)科學(xué)中的基本概念，在理論推導(dǎo)中，學(xué)者們?cè)O(shè)計(jì)了各種不同的規(guī)則執(zhí)行方式，例如，串行模式[16]、極小并行模式[17]、極大并行模式[18]和扁平極大并行模式[19]. 在理論分析方面，主要通過與圖靈機(jī)比較來(lái)證明多數(shù)膜系統(tǒng)是具有圖靈完備性的，即這些P系統(tǒng)的計(jì)算能力與通用圖靈機(jī)等價(jià)[20-24]. 同時(shí)，受細(xì)胞膜的分離、分裂以及生成等生物活動(dòng)的啟發(fā)，膜系統(tǒng)中存在細(xì)胞分離[1](1)Sosík P, Cienciala L. Computational power of cell separation in tissue P systems[J]. Information Sciences, 2014, 279: 805-815.、 細(xì)胞分裂[25]以及細(xì)胞生成[26]等規(guī)則，通過這些規(guī)則的使用，細(xì)胞可以生成指數(shù)多個(gè)細(xì)胞，通過以空間換取時(shí)間的方式有效地求解NP完全問題[27-29]以及PSPACE完全問題[30-34]. 另一方面，研究膜計(jì)算的實(shí)際應(yīng)用也非常有趣[35-37]，例如，P系統(tǒng)可以應(yīng)用到生物系統(tǒng)和合成生物學(xué)[38]中，可以改進(jìn)人工智能算法[39-43]，還可以用于電路系統(tǒng)的設(shè)計(jì)以及生態(tài)系統(tǒng)的建模[44-45]. 關(guān)于P系統(tǒng)的詳細(xì)信息，讀者可以查閱文獻(xiàn)[46]. 更詳盡的細(xì)節(jié)以及最新的參考資料可以在網(wǎng)址http://ppage.psystems.eu 上找到.

通訊P系統(tǒng)是一類受活細(xì)胞中物質(zhì)跨膜移動(dòng)的生物現(xiàn)象啟發(fā)而得來(lái)的膜系統(tǒng)，最早提出來(lái)是在文獻(xiàn)[47]中. 這類P 系統(tǒng)是一類通過使用同向/異向轉(zhuǎn)運(yùn)規(guī)則代替進(jìn)化規(guī)則的計(jì)算模型，其中,同向轉(zhuǎn)運(yùn)規(guī)則的形式是(u,in) 或者(u,out)，異向轉(zhuǎn)運(yùn)規(guī)則的形式是(u,out;v,in). 該類P系統(tǒng)的計(jì)算理論研究廣泛，比如計(jì)算能力[48-50]，計(jì)算有效性[51]和生成語(yǔ)言的能力[52].

膜計(jì)算中有一類通訊P系統(tǒng)被提出并且得到了深入的研究，這里稱為帶有通道狀態(tài)的通訊P系統(tǒng)，其中，通道上的狀態(tài)用來(lái)控制細(xì)胞間的通訊以及細(xì)胞與環(huán)境間的通訊. 對(duì)于通訊，如果從不同的角度來(lái)看，那么會(huì)有兩種情況：其一，細(xì)胞間會(huì)有與狀態(tài)相關(guān)的鏈接，并且細(xì)胞會(huì)使用這些狀態(tài)來(lái)控制細(xì)胞間的通訊；其二， 通訊的完成通過同向/異向規(guī)則的使用. 本文主要圍繞著帶有通道狀態(tài)的通訊P 系統(tǒng).首先，對(duì)帶有通道狀態(tài)的細(xì)胞型通訊P系統(tǒng)，帶有通道狀態(tài)的組織型通訊P系統(tǒng)以及帶有通道狀態(tài)的識(shí)別通訊P系統(tǒng)的基本概念進(jìn)行了簡(jiǎn)單的介紹；其次，對(duì)這兩類通訊P系統(tǒng)的計(jì)算能力和計(jì)算復(fù)雜性分別進(jìn)行了概述；最后，給出了對(duì)這類通訊P 系統(tǒng)的總結(jié)以及對(duì)未來(lái)的展望.

1 帶有通道狀態(tài)通訊膜系統(tǒng)的基本概念

本節(jié)主要介紹帶有通道狀態(tài)的細(xì)胞型和組織型通訊P系統(tǒng)的概念，模型中涉及有關(guān)形式語(yǔ)言的知識(shí)，讀者可以參考文獻(xiàn)[53].

1.1 帶有通道狀態(tài)的通訊膜系統(tǒng)

帶有通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)是由Song等[54]首次提出的，該模型使用的是帶有通道狀態(tài)的同向/異向轉(zhuǎn)運(yùn)規(guī)則，且規(guī)則以極大并行的方式執(zhí)行，具體概念如下.

定義1一個(gè)度為q≥1的帶有通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

?Γ是一個(gè)有限字母表，ε?Γ；

?K是一個(gè)狀態(tài)字母表(與Γ的交集為空)；

?μ是一個(gè)含有q個(gè)節(jié)點(diǎn)的根樹，用1,…,q來(lái)標(biāo)記；

?si(1≤i≤q)是通道狀態(tài)；

- 同向規(guī)則：(s,(u,out),s′)或(s,(u,in),s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,(u,out;v,in),s′)，s,s′∈K，u,v∈Γ+；

?iout∈{0,1,…,q}.

規(guī)則(u,out)，(u,in)(或(u,out;v,in))的長(zhǎng)度定義為|u|(或|u|+|v|).

筆者注意到一個(gè)非常重要的限制是兩個(gè)相鄰區(qū)域之間最多一個(gè)通道，每個(gè)步驟的狀態(tài)都來(lái)自于K. 這個(gè)不會(huì)限制相鄰區(qū)域間的通訊，因?yàn)橐粋€(gè)通道的兩個(gè)方向上都允許物質(zhì)的移動(dòng).

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且膜i中包含多重集合u，那么此時(shí)在格局中應(yīng)用一條同向規(guī)則(s,(u,out),s′). 當(dāng)這樣一條同向轉(zhuǎn)運(yùn)規(guī)則被應(yīng)用時(shí)，多重集合u被發(fā)送到區(qū)域p(i)，且區(qū)域i和區(qū)域p(i)之間的通道狀態(tài)從s變?yōu)閟′.

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且區(qū)域p(i)中包含多重集合u，那么此時(shí)在一個(gè)格局中應(yīng)用一條同向轉(zhuǎn)運(yùn)規(guī)則(s,(u,out),s′). 當(dāng)這樣一條規(guī)則被應(yīng)用時(shí)，多重集合u將從區(qū)域p(i) 進(jìn)入膜i中，且區(qū)域i與區(qū)域p(i)之間的通道狀態(tài)由s變?yōu)閟′.

如果膜i和它的父區(qū)域p(i)之間的通道狀態(tài)為s，且膜i中包含多重集合u，同時(shí)膜i的父區(qū)域中包含多重集合v，那么此時(shí)在一個(gè)格局中應(yīng)用一條反向轉(zhuǎn)運(yùn)規(guī)則(s,(u,out;v,in),s′). 當(dāng)使用這樣一條規(guī)則時(shí)，多重集合u從膜i發(fā)送到區(qū)域p(i)，同時(shí)，多重集合v從區(qū)域p(i)發(fā)送到膜i，且區(qū)域i與區(qū)域p(i)之間的通道狀態(tài)由s變?yōu)閟′.

已經(jīng)證明了該類型P系統(tǒng)具有圖靈通用性. 除此之外，學(xué)者們還提出了具有細(xì)胞分裂的帶有通道狀態(tài)的細(xì)胞型P 系統(tǒng)[55]，同樣已經(jīng)證明具有圖靈通用性，且此類型膜系統(tǒng)還可以解決哈密頓回路問題.

帶有通道狀態(tài)的組織型通訊P系統(tǒng)是由Freund等[56]首次提出的，該模型使用的是帶有通道狀態(tài)的同向/異向轉(zhuǎn)運(yùn)規(guī)則，且規(guī)則以極大并行的方式執(zhí)行，具體概念如下.

定義2一個(gè)度為q≥1的帶通道狀態(tài)的組織型通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,,iout),

其中：

?Γ是一個(gè)有限字母；

?T?Γ是一個(gè)結(jié)束物質(zhì)的字母表；

?K是一個(gè)狀態(tài)的字母表；

?ε?Γ是初始時(shí)刻位于環(huán)境中的物質(zhì)集合，所有可用的物質(zhì)都有任意多的數(shù)量；

?ch?{(i,j)|i,j∈{0,…,q},i≠j}是細(xì)胞間通道或細(xì)胞與環(huán)境間通道的集合，在ch中最多出現(xiàn)(i,j)，(j,i)其中之一(0標(biāo)記環(huán)境)；

?R(i,j)是具有如下形式的有限規(guī)則集合(與通道(i,j)∈ch有關(guān))：

- 同向規(guī)則：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

?iout∈{0,1,…,q}.

筆者注意到一個(gè)重要的限制是兩個(gè)已給細(xì)胞之間最多存在一條通道，通道以有序?qū)?i,j)的形式給出，并且通道上有來(lái)自于K的狀態(tài). 這個(gè)不會(huì)限制兩個(gè)細(xì)胞間或者細(xì)胞和環(huán)境之間的通訊，因?yàn)橥ǖ郎系膬蓚€(gè)方向都允許物質(zhì)的移動(dòng). 規(guī)則(s,u/λ,s′)、(s,λ/u,s′) 或者(s,u/v,s′)的長(zhǎng)度分別為|u|和|u|+|v|.

如果區(qū)域i和區(qū)域j之間通道的狀態(tài)為s，且區(qū)域i包含對(duì)象的多重集合u，(或者區(qū)域j包含對(duì)象的多重集合u)，那么此時(shí)在一個(gè)格局中使用同向規(guī)則(s,u/λ,s′)∈Ri,j(或(s,λ/u,s′)∈Ri,j). 當(dāng)使用這樣的規(guī)則時(shí)，多重集合u被發(fā)送到區(qū)域j(或者區(qū)域i)，且區(qū)域i和區(qū)域j之間的通道狀態(tài)由s變?yōu)閟′.

如果區(qū)域i和區(qū)域j之間通道的狀態(tài)為s，且區(qū)域i包含對(duì)象的多重集合u，同時(shí)區(qū)域j包含對(duì)象的多重集合v，那么此時(shí)在一個(gè)格局中使用異向規(guī)則(s,u/v,s′)∈Ri,j. 當(dāng)使用這樣的規(guī)則時(shí)，多重集合u將從區(qū)域i發(fā)送到區(qū)域j，多重集合v將從區(qū)域j發(fā)送到區(qū)域i，且區(qū)域i和區(qū)域j之間的通道狀態(tài)由s變?yōu)閟′.

已經(jīng)證明該系統(tǒng)具有圖靈通用性. 除此之外，學(xué)者們還提出了帶有細(xì)胞分裂的帶通道狀態(tài)的組織型通訊P 系統(tǒng)，單向[57-59]帶有細(xì)胞分裂帶通道狀態(tài)的組織型通訊P系統(tǒng)[60]，它們不僅具有圖靈通用性，而且可以解決NP完全問題.

下面將介紹帶有細(xì)胞分裂和通道狀態(tài)的通訊P系統(tǒng)以及相應(yīng)的識(shí)別P系統(tǒng)的基本概念.

1.2 帶細(xì)胞分裂和通道狀態(tài)的通訊膜系統(tǒng)

定義3一個(gè)度為q≥1的帶細(xì)胞分裂和通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,K,ε,μ,1,…,q,s1,…,sq,1,…,q,iout),

其中：

?Γ是一個(gè)物質(zhì)(或符號(hào))的字母表，又稱為一個(gè)有限非空集合；

?K是一個(gè)通道狀態(tài)的字母表，表示一個(gè)有限非空集合且?！蒏=?；

?ε是Γ的一個(gè)子集，代表初始位于Π環(huán)境中的物質(zhì)集合；

?μ是一個(gè)由1,…,q標(biāo)記的有q個(gè)節(jié)點(diǎn)的根樹，表示這個(gè)系統(tǒng)的框架；

?si，1≤i≤q是K上的通道狀態(tài)，它們代表每個(gè)區(qū)域的初始狀態(tài)；

?Ri，1≤i≤q是每個(gè)區(qū)域i中規(guī)則的有限集，有下述的形式：

- 通訊規(guī)則：

- 同向規(guī)則：(s,(u,out),s′)或(s,(u,in),s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,(u,out;v,in),s′)，s,s′∈K，u,v∈Γ+；

- 分裂規(guī)則：[a]i→[b]i[c]i，a,b,c∈Γ，i∈{2,…,q}，i≠iout.

?iout∈{0,1,…,q}是輸出區(qū)域.

定義4 一個(gè)度為q≥1的帶細(xì)胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,T,K,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout),

其中：

?Γ是一個(gè)有限字母；

?T?Γ是一個(gè)終止字母表；

?K是一個(gè)狀態(tài)的字母表；

?ε?Γ是初始時(shí)刻位于環(huán)境中的物質(zhì)集合，所有可用的物質(zhì)都有任意多的數(shù)量；

?ch?{(i,j)|i,j∈{0,…,q},i≠j}是細(xì)胞間通道或細(xì)胞與環(huán)境間通道的集合;

?R(i,j)是具有如下形式的有限規(guī)則集合(與通道(i,j)∈ch有關(guān))：

- 通訊規(guī)則：

- 同向規(guī)則：(s,u/λ,s′)，s,s′∈K，u∈Γ+；

- 異向規(guī)則：(s,u/v,s′)，s,s′∈K，u,v∈Γ+，|u|>0，|v|>0；

- 分裂規(guī)則：

- [a]i→[b]i[c]i，a,b,c∈Γ，i∈{1,…,q}，i≠iout；

?iout∈{0,1,…,q}是輸出區(qū)域.

1.3 帶細(xì)胞分裂和通道狀態(tài)的識(shí)別通訊膜系統(tǒng)

定義5一個(gè)度為q≥1的帶有細(xì)胞分裂和通道狀態(tài)的細(xì)胞型識(shí)別通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iin,iout),

其中：

?(Γ,K,ε,μ,∑,1,…,q,s1,…,sq,1,…,q,iout) 是一個(gè)度q≥1的帶有細(xì)胞分裂和通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)；

?Γ有兩個(gè)不同的物質(zhì)yes和no；

?∑是一個(gè)嚴(yán)格包含于Γ中的輸入字母表，使得ε?Γ∑；

?iin∈{1,…,q}是輸入細(xì)胞，且iout=0；

?所有的計(jì)算停止；

在這個(gè)系統(tǒng)中，規(guī)則的集合中包含細(xì)胞分裂規(guī)則，即可以產(chǎn)生2n個(gè)細(xì)胞，由此可見這個(gè)系統(tǒng)可以采用空間換時(shí)間的方式來(lái)解決HPP問題.

定義6一個(gè)度為q≥1的帶有細(xì)胞分裂和通道狀態(tài)的組織型識(shí)別通訊膜系統(tǒng)是一個(gè)元組

Π=(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iin,iout),

其中：

?(Γ,T,K,∑,ε,1,…,q,ch,(s(i,j))(i,j)∈ch,(R(i,j))(i,j)∈ch,iout) 是一個(gè)度q≥1的帶有細(xì)胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)；

?Γ有兩個(gè)不同的物質(zhì)yes和no；

?∑是一個(gè)嚴(yán)格包含于Γ中的輸入字母表；

?iin∈{1,…,q}是輸入細(xì)胞，且iout=0；

?所有的計(jì)算停止；

在這個(gè)系統(tǒng)中，規(guī)則的集合中包含細(xì)胞分裂規(guī)則，即可以產(chǎn)生2n個(gè)細(xì)胞，由此可見這個(gè)系統(tǒng)可以采取空間換時(shí)間的方式來(lái)解決SAT問題.

對(duì)于帶有細(xì)胞分裂和通道狀態(tài)的識(shí)別通訊膜系統(tǒng)來(lái)說(shuō)，如果物質(zhì)yes出現(xiàn)在與計(jì)算停止?fàn)顟B(tài)相關(guān)的環(huán)境中，且在計(jì)算的非停止?fàn)顟B(tài)中沒有出現(xiàn)物質(zhì)yes和no，那么就稱計(jì)算為一個(gè)接受計(jì)算，否則，就稱計(jì)算為拒絕計(jì)算.

2 帶通道狀態(tài)通訊膜系統(tǒng)的計(jì)算能力和計(jì)算復(fù)雜性

本節(jié)首先介紹帶有細(xì)胞分裂和通道狀態(tài)的通訊P系統(tǒng)求解判定性問題的概念，然后再分析這些膜系統(tǒng)的計(jì)算能力，最后給出這些膜系統(tǒng)的計(jì)算復(fù)雜性.

接下來(lái)，根據(jù)文獻(xiàn)[61]，筆者定義用同向/異向規(guī)則的帶有細(xì)胞分裂和通道狀態(tài)的識(shí)別通訊膜系統(tǒng)在統(tǒng)一模式下求解判定性問題.

定義7在多項(xiàng)式時(shí)間內(nèi)可以由一族帶有細(xì)胞分裂和通道狀態(tài)的識(shí)別通訊膜系統(tǒng)∏={Π(n)|n∈}以一種統(tǒng)一的模式解決一個(gè)判定性問題X=(IX,θX)，如果滿足下述的條件：

?一族∏是通過圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)統(tǒng)一的，也就是說(shuō)存在一個(gè)多項(xiàng)式時(shí)間內(nèi)工作的確定性圖靈機(jī)，且這個(gè)確定性圖靈機(jī)可以構(gòu)建系統(tǒng)Π(n)(n∈)；

?在IX上存在一個(gè)多項(xiàng)式時(shí)間的計(jì)算函數(shù)對(duì)(cod,s)，使得

- 對(duì)于每一個(gè)例子u∈IX來(lái)說(shuō)，s(u)是一個(gè)自然數(shù)，cod(u) 是系統(tǒng)Πs(u)上的一個(gè)輸入多重集；

- 對(duì)每個(gè)自然數(shù)n∈來(lái)說(shuō)，s-1(n)是一個(gè)有限集合；

- 系統(tǒng)族∏是關(guān)于(X,cod,s) 多項(xiàng)式有界的，也就是說(shuō)存在一個(gè)多項(xiàng)式函數(shù)p(n)，使得對(duì)每一個(gè)u∈IX來(lái)說(shuō)，系統(tǒng)Π(s(u)+cod(u))的每一個(gè)計(jì)算都在最多p(|u|)步內(nèi)停止；

- 系統(tǒng)族∏是關(guān)于(X,cod,s) 充分的，即對(duì)每一個(gè)u∈IX來(lái)說(shuō)，如果系統(tǒng)Π(s(u)+cod(u))存在一個(gè)接受的計(jì)算，那么θX(u)=1；

- 系統(tǒng)族∏是關(guān)于(X,cod,s) 完備的，即對(duì)每一個(gè)u∈IX來(lái)說(shuō)，如果θX(u)=1，那么系統(tǒng)Π(s(u)+cod(u)) 的每一個(gè)計(jì)算都是一個(gè)接受的計(jì)算.

2.1 帶有通道狀態(tài)的通訊膜系統(tǒng)的計(jì)算能力

本小節(jié)首先介紹帶有通道狀態(tài)的類細(xì)胞或類組織通訊膜系統(tǒng)的計(jì)算能力，然后再分別介紹了帶有細(xì)胞分裂和通道狀態(tài)的類細(xì)胞或類組織通訊膜系統(tǒng)的計(jì)算復(fù)雜性問題.

在介紹定理之前，首先給出各種符號(hào)的含義. 一般，NFIN表示正整數(shù)所有有限集的族，NMAT表示無(wú)外觀檢測(cè)矩陣文法產(chǎn)生的正整數(shù)集合的族，NRE表示自然數(shù)遞歸可枚舉集的族.

根據(jù)文獻(xiàn)[54-55]，對(duì)于帶有通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)，筆者有如下的定理展現(xiàn)其計(jì)算能力.

定理1根據(jù)文獻(xiàn)[54]，對(duì)于帶有通道狀態(tài)，使用同向/異向規(guī)則的細(xì)胞型通訊膜系統(tǒng)來(lái)說(shuō)，其具有如下的計(jì)算能力，其中，NOPm(statek,symt1,antit2)表示該類膜系統(tǒng)計(jì)算的所有數(shù)字集合的族，且該類膜系統(tǒng)有m個(gè)膜，k個(gè)狀態(tài)，以及使用規(guī)則長(zhǎng)度最長(zhǎng)為t1的同向規(guī)則和規(guī)則長(zhǎng)度最長(zhǎng)為t2的異向規(guī)則. 如果在膜系統(tǒng)中只使用了同向規(guī)則(或者異向規(guī)則)，那么由膜系統(tǒng)計(jì)算得來(lái)的所有數(shù)字集合的族簡(jiǎn)單地記為NOPm(statek,symt1)(或者NOPm(statek,antit2)).如果參數(shù)m,k,t1,t2沒有限制，那么它們可以用*來(lái)代替.

?NOP*(state*,anti2)?NFIN；

?NOP*(state2,sym1)?NFIN；

?NOP1(state1,anti4)=NOP1(state*,sym1,anti2) =NMAT；

?NOP2(state*,sym1)=NRE；

?NOP2(state4,anti2)=NRE；

?NOP2(state2,anti3)=NRE；

?NOP2(state1,anti3)=NRE；

?NOP2(state3,sym1,anti2) =NRE.

定理2根據(jù)文獻(xiàn)[55]，對(duì)于帶有通道狀態(tài)，使用協(xié)同同向規(guī)則，工作在扁平極大并行模式的細(xì)胞型通訊膜系統(tǒng)來(lái)說(shuō)，其具有如下的計(jì)算能力，其中，NOPm(statek,symt,flat)表示由m個(gè)膜，k個(gè)狀態(tài)，只使用規(guī)則長(zhǎng)度最長(zhǎng)為t的同向規(guī)則組成且以扁平極大并行方式工作的膜系統(tǒng)計(jì)算的所有自然數(shù)集合的族. 如果參數(shù)m,k,t沒有限制，那么它們可以用*來(lái)代替.

?NOP2(state*,sym1,flat)=NOP2(state4,sym2,flat)=NOP2(state2,sym3,flat)=NRE；

?NOP1(state1,sym3,flat)=NRE；

?NOP1(state*,sym2,flat)=NRE；

?NOP2(state3,sym2,flat)=NRE.

定理3根據(jù)文獻(xiàn)[56]，對(duì)于帶有通道狀態(tài)的組織型通訊膜系統(tǒng)來(lái)說(shuō)，其具有如下的計(jì)算能力. 一般來(lái)說(shuō)，系統(tǒng)Π計(jì)算得來(lái)的所有向量的集合使用Ps(Π)來(lái)表示.PsOtpm(statek,antii)表示系統(tǒng)計(jì)算的向量集合Ps(Π)的族，其中這個(gè)系統(tǒng)有m個(gè)細(xì)胞，k個(gè)狀態(tài)，使用形式為(s,x/y,s′)的規(guī)則，|x|≤i，|y|≤i. 當(dāng)參數(shù)m,k,i沒有限制時(shí)，可以使用*來(lái)代替.MAT表示矩陣文法生成的語(yǔ)言族且PsCF?PsMAT?PsRE.

?PsMAT?PsOtp1(state*,anti1)；

?PsMAT?PsOtp1(state1,anti2)；

?PsOtp1(state*,anti*)?PsMAT；

?PsMAT=PsOtp1(statek,antii)=PsOtp1(state*,antij)，k≥1，i≥2，j≥1，每個(gè)k,i,j也可以等于*；

?PsRE=PsOtpm(state*,antii)，m≥2，i≥1；

?PsRE=PsOtpm(statek,antii)，m≥2，k≥1，i≥2；

?PsRE=PsOtp*(statek,antii)，k≥3，i≥1.

定理4根據(jù)文獻(xiàn)[59]，對(duì)于帶有通道狀態(tài)，工作在扁平極大并行模式下的組織型通訊膜系統(tǒng)來(lái)說(shuō)，其具有如下的計(jì)算能力. 系統(tǒng)Π計(jì)算得來(lái)的所有向量的集合使用Ps(Π)來(lái)表示.PsOtpm(statek,symt1,antit2,flat)表示系統(tǒng)計(jì)算的向量集合的族，其中，這個(gè)系統(tǒng)有m個(gè)細(xì)胞，k個(gè)狀態(tài)，使用規(guī)則長(zhǎng)度最長(zhǎng)為t1的同向規(guī)則和規(guī)則長(zhǎng)度最長(zhǎng)為t2的異向規(guī)則，flat表示通道上的規(guī)則以扁平極大并行的方式使用. 當(dāng)參數(shù)m,k,i沒有限制時(shí)，可以使用*來(lái)代替.

?PsOtp*(state*,anti2,flat)?PsFIN；

?PsOtp1(state1,sym3,flat)=PsRE；

?PsOtp2(state*,sym1,flat)=PsRE；

?PsOtp*(state4,sym1,flat)=PsRE.

?NOtP2m(state*,sym1)=NRE；

?NOtP2m(state4,sym2)=NRE；

?NOtP*m(state5,sym1)=NRE.

2.2 帶有細(xì)胞分裂和通道狀態(tài)的通訊膜系統(tǒng)的計(jì)算復(fù)雜性

定理6 根據(jù)文獻(xiàn)[55]，帶有細(xì)胞分裂和通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)可以解決哈密頓回路問題，其計(jì)算復(fù)雜性如下，CCDeP(k)表示一類帶有細(xì)胞分裂和通道狀態(tài)，通訊規(guī)則長(zhǎng)度最長(zhǎng)為k的細(xì)胞型通訊膜系統(tǒng)，PMCCCDeP(k)表示由CCDeP(k)在多項(xiàng)式時(shí)間內(nèi)解決的所有判定性問題的集合.

?HPP∈PMCCCDeP(1)；

?NP∪co-NP?PMCCCDeP(1).

定理7根據(jù)文獻(xiàn)[59]，帶有細(xì)胞分裂和通道狀態(tài)，工作在扁平極大并行模式下的組織型通訊膜系統(tǒng)可以解決SAT問題，其計(jì)算復(fù)雜性如下，PMCTSDC(k)來(lái)表示由帶有細(xì)胞分裂和通道狀態(tài)，通訊規(guī)則長(zhǎng)度最長(zhǎng)為k的組織型識(shí)別通訊膜系統(tǒng)在多項(xiàng)式時(shí)間內(nèi)以統(tǒng)一的方式解決的所有判定性問題的集合.

3 結(jié)論與展望

本文主要介紹了帶有通道狀態(tài)的通訊膜系統(tǒng)，包括帶有通道狀態(tài)的細(xì)胞型通訊膜系統(tǒng)和帶有通道狀態(tài)的組織型通訊膜系統(tǒng). 本文首先分別對(duì)這兩類膜系統(tǒng)的基本概念做了簡(jiǎn)要的介紹；其次分別介紹了帶有通道狀態(tài)的通訊膜系統(tǒng)的一些變形：帶細(xì)胞分裂和通道狀態(tài)的組織型識(shí)別通訊膜系統(tǒng)，帶細(xì)胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng)，帶細(xì)胞分裂和通道狀態(tài)的細(xì)胞型識(shí)別通訊膜系統(tǒng)，以及帶細(xì)胞分裂和通道狀態(tài)的組織型通訊膜系統(tǒng). 對(duì)于這些膜系統(tǒng)，它們具有解決判定性問題的能力，本文分析了這些模型的計(jì)算能力和計(jì)算復(fù)雜性. 至今為止，膜計(jì)算作為自然計(jì)算中的一個(gè)分支，仍然是一個(gè)冉冉新生的計(jì)算模型，對(duì)于帶通道狀態(tài)的通訊膜系統(tǒng)來(lái)說(shuō)，存在如下待解決的問題，且這些問題值得思考，具體如下.

(1)以串行方式工作的帶通道狀態(tài)，使用同向/異向規(guī)則的細(xì)胞型P系統(tǒng)已經(jīng)在文獻(xiàn)[52]中得以研究；以扁平極大并行方式工作，帶有通道狀態(tài)的通訊P 系統(tǒng)的通用性也得到了研究，在這項(xiàng)工作中同時(shí)獲得了NP完全問題的一個(gè)解. 然而值得關(guān)注的是在一些其他的操作策略中，如異步模式，無(wú)時(shí)間模式[62-64]，或者集合推導(dǎo)模式[65]下帶有細(xì)胞分裂和通道狀態(tài)的P系統(tǒng)的計(jì)算能力或者計(jì)算效率.

(2)可以將膜分離(或裂變)作為一種生物現(xiàn)象納入P系統(tǒng)中，它能夠在多項(xiàng)式時(shí)間內(nèi)產(chǎn)生大量的新細(xì)胞為計(jì)算提供一個(gè)指數(shù)級(jí)的工作空間，因此，有膜分離的各種形式的P系統(tǒng)可以解決NP完全問題[66-67]. 在文獻(xiàn)[68]中，HPP問題可以由工作在極大并行模式，有活性膜和分離規(guī)則的P系統(tǒng)解決，然而，HPP 問題是否能由帶細(xì)胞分離和通道狀態(tài)的通訊P系統(tǒng)來(lái)解決值得思考.

(3)由于PSPACE問題，如QSAT問題可以由帶有非基本膜分裂，使用通訊規(guī)則(同向/異向規(guī)則)的P系統(tǒng)高效地解決[30]. 因此，假設(shè)帶有非基本膜分裂和通道狀態(tài)的通訊P 系統(tǒng)也可以解決PSPACE問題，而如何解決仍然有待于思考.

(4)對(duì)于帶通道狀態(tài)的組織型通訊P系統(tǒng)來(lái)說(shuō)，研究其工作在扁平極大并行模式下，且使用細(xì)胞分離規(guī)則的系統(tǒng)的計(jì)算能力和計(jì)算復(fù)雜性是一個(gè)有待于被解決的問題；

(5)依據(jù)各種生物活動(dòng)特性，研究者們提出了串行模式、極小并行模式、極大并行模式以及扁平極大并行模式. 對(duì)于帶有通道狀態(tài)的通訊P系統(tǒng)來(lái)說(shuō)，分別研究其在不同模式下的計(jì)算能力和計(jì)算復(fù)雜性是一個(gè)有待于解決的問題.