網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)的計(jì)算能力研究.pdf

1、隨著科學(xué)的不斷發(fā)展，目前的科學(xué)研究經(jīng)常涉及到多個(gè)不同的學(xué)科領(lǐng)域，打破經(jīng)典學(xué)科的分類，進(jìn)行交叉學(xué)科的研究成為大勢(shì)所趨。在計(jì)算機(jī)科學(xué)領(lǐng)域，生物學(xué)一直對(duì)其發(fā)展有重大的影響，許多計(jì)算思想、模型、方法都是受生物系統(tǒng)的啟發(fā)而來(lái)，如自然計(jì)算中為大家所熟悉的遺傳算法和神經(jīng)計(jì)算等。1998年，Gh．Pǎaun教授首次提出了膜計(jì)算的概念。膜計(jì)算是自然計(jì)算的一個(gè)新的分支，是計(jì)算機(jī)科學(xué)、生物學(xué)、數(shù)學(xué)等多學(xué)科交叉的研究領(lǐng)域，其目的是從細(xì)胞的結(jié)構(gòu)和功能，以及從組織

2、和器官等細(xì)胞群相互協(xié)作處理信息的方式中，獲得新的思想，設(shè)計(jì)新的模型。膜計(jì)算是根據(jù)細(xì)胞處理化學(xué)物質(zhì)的機(jī)理提出的一種新的計(jì)算模式，膜計(jì)算系統(tǒng)（由于Gh．Pǎaun院士對(duì)膜計(jì)算領(lǐng)域的巨大貢獻(xiàn)，也稱為P系統(tǒng)）具有良好的分布式結(jié)構(gòu)和巨大的并行性，并且為生物系統(tǒng)的建模與仿真提供了新的工具。根據(jù)膜結(jié)構(gòu)的不同，膜系統(tǒng)分為嵌套結(jié)構(gòu)膜系統(tǒng)和網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)。本文研究網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)，它包括組織膜系統(tǒng)和脈沖神經(jīng)膜系統(tǒng)。組織膜系統(tǒng)是依據(jù)組織中細(xì)胞之間通過(guò)蛋白質(zhì)通道

3、進(jìn)行通信的生物事實(shí)構(gòu)造的計(jì)算模型，而脈沖神經(jīng)膜系統(tǒng)則是基于大腦中神經(jīng)元之間通過(guò)突觸相互協(xié)作、處理脈沖信息的生物現(xiàn)象而抽象出來(lái)的計(jì)算模型。由于其強(qiáng)大的計(jì)算能力及其在解決困難問(wèn)題方面顯示的潛力，網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)引起越來(lái)越多學(xué)者的關(guān)注。
　　 本文從語(yǔ)言的產(chǎn)生能力及數(shù)的識(shí)別能力、小通用性以及計(jì)算有效性三個(gè)方面研究了網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)的計(jì)算能力，主要工作如下：首先研究了網(wǎng)狀結(jié)構(gòu)膜系統(tǒng)的語(yǔ)言產(chǎn)生能力和數(shù)的識(shí)別能力。計(jì)算設(shè)備的語(yǔ)言產(chǎn)生及數(shù)的識(shí)別能

4、力是研究計(jì)算設(shè)備計(jì)算能力的基本問(wèn)題之一。本文研究了窮舉使用規(guī)則的脈沖神經(jīng)膜系統(tǒng)產(chǎn)生二進(jìn)制字符串語(yǔ)言的能力，以及前瞻模式下的組織膜系統(tǒng)識(shí)別數(shù)的能力。對(duì)于窮舉使用規(guī)則的脈沖神經(jīng)膜系統(tǒng)，研究了它在使用擴(kuò)展規(guī)則時(shí)的二進(jìn)制語(yǔ)言產(chǎn)生能力，證明了擴(kuò)展脈沖神經(jīng)膜系統(tǒng)在窮舉使用規(guī)則的模式下可以刻畫有限語(yǔ)言和遞歸可枚舉語(yǔ)言。另外研究了前瞻模式下的組織膜系統(tǒng)作為數(shù)的識(shí)別裝置時(shí)的識(shí)別能力，證明了在前瞻使用規(guī)則的模式下，包含3個(gè)細(xì)胞的組織膜系統(tǒng)可以刻畫遞歸可枚舉

5、數(shù)集。其次對(duì)具有反脈沖的脈沖神經(jīng)膜系統(tǒng)的小通用性進(jìn)行了研究。計(jì)算模型的小通用性是計(jì)算機(jī)科學(xué)中經(jīng)典的研究問(wèn)題之一，小通用系統(tǒng)具有良好的通用性和擴(kuò)展性，可以直接作為實(shí)用系統(tǒng)的一個(gè)核心部件，也可以協(xié)助開(kāi)發(fā)系統(tǒng)，節(jié)約系統(tǒng)成本，縮短研發(fā)周期。對(duì)于脈沖神經(jīng)膜系統(tǒng)而言，研究小通用性問(wèn)題除了具有計(jì)算機(jī)科學(xué)意義外，還有其生物學(xué)意義：給出某種小通用“腦”的度量。本文對(duì)脈沖神經(jīng)膜系統(tǒng)的小通用性進(jìn)行了如下研究：在作為計(jì)算函數(shù)的裝置的情形下，本文分別構(gòu)造了使用規(guī)

6、則產(chǎn)生反脈沖和使用抑制突觸產(chǎn)生反脈沖的小通用脈沖神經(jīng)膜系統(tǒng)，并通過(guò)考慮共用附屬神經(jīng)元的方式，優(yōu)化了所得到的小通用系統(tǒng)的神經(jīng)元個(gè)數(shù)。這一結(jié)論給出了具有反脈沖，并且使用純規(guī)則的小通用“腦”的度量。最后研究了組織膜系統(tǒng)的計(jì)算有效性。由于組織膜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是固定的，因此在計(jì)算過(guò)程中無(wú)法由組織膜系統(tǒng)本身來(lái)生成計(jì)算空間，從而實(shí)現(xiàn)空間換時(shí)間。本文研究了組織膜系統(tǒng)在具有細(xì)胞分割性質(zhì)時(shí)的計(jì)算有效性。利用這種類型的系統(tǒng)，求解了一個(gè)著名的NP完全問(wèn)題---