P System （P系統）是一種仿生物技術的計算模型，它建立在生物細胞的結構基礎之上，由細胞處理化學物質的機理抽象而來。P System的思想最初在1998年由羅馬尼亞的計算機科學家Gheorghe Paun提出，P System正是由他的姓氏(Paun)而得名。之後，各類基於P System的模型層出不窮，導致了一個新的研究領域 - “膜計算”的誕生。
基本介紹
- 中文名：P系統
- 外文名：P System
- 釋義：是一種仿生物技術的計算模型
- 提出時間：1998年
模型概述,模型構成,模型計算,計算示例,
模型概述
就像在真實的生物細胞里一樣，化學反應只有在反應物相接觸（有時會有催化劑）的時候才會發生，而由於P System的規則是隨機套用的，這導致了計算結果的不確定性，換句話說，同一問題的重複的計算可能導致多個解決方案的產生。
P System的完成時，所有最外層膜外的化學物質將會達到穩態，也就是沒有反應再繼續發生了。
模型構成
儘管現在隨著套用領域的不斷擴展，P System的結構日趨多樣，但是其基本的組件還是大致相同的。系統中每一個元素都有它特定的角色，而且基本上都可以在生物細胞中找到它們的原形。
環境（The environment）
環境是指P System的外部環境。在P System的初始狀態下，環境只包括了容器膜。隨著計算的進行，不斷有些物質被傳入環境，在計算完成時，環境中的物質就被認為是計算的“結果”。
膜（Membranes）
膜是P System中最主要的結構，一個膜結構就是一個包含一系列物質、規則和其他膜的游離單元。最外層被環境包含的膜被稱為容器膜（container membrane）或者表面膜（skin membrane）。顧名思義，我們稱之為“膜”（而不叫牆），因為它是具有滲透性的。某些由規則產生的物質可以穿過它們。除了容器膜之外，其他膜都可以分解，這時膜內的物質會被歸屬到包含這層膜的外層膜，除非規則令它們消失掉了。有些P System還允許膜分裂，擁有選擇滲透性或者具有各種厚度。
物質（Objects）
這裡物質可以被認為是反應物，它們將會和其他化學物質發生反應產生某些生成物（產品），他們在P系統中都有對應的符號（Symbols）表示。在P System中每一類型的符號由不同的字母標示，所以膜的內容可以用一個字元串表示。儘管由於地區差異，這個符號系統現在有很多版本，但是一些特殊符號還是存在的，它們是默認約定好的，例如一個小寫的delta(δ)通常是用在輸出規則中表示初始化膜的分解。
催化劑（Catalysts）
催化劑是P System中比較特殊的一種物質，和化學上所說的催化劑類似，它們在反應中不會被消耗掉，但它們可能是反應發生的必要條件。
規則（Rules）
規則就像一條條反應式，代表了膜內發生反應的種種可能，它們導致膜狀態的變化。一條規則需要一組輸入對象（符號或催化劑）並通過規則（反應）生成一組輸出對象。規則之間可以有優先權的區分，這也意味著較低優先權的規則只會在較高優先權規則不能套用的情況下（如缺少必須的符號）才能得以運行。
在一個基本的P System中，規則處理輸出對象的方式有三種。通常，輸出對象就釋放到當前膜（即規則和當前輸入對象駐留的膜）內，這類規則我們稱之為“here”規則。另外兩種方式是in規則和out規則：in操作使得生成對象被傳入到當前膜的某個子膜中去，在計算過程中in操作是隨機發生的；out操作使得物質被傳到當前膜的父膜或者某個兄弟膜中，具體需要由實際的P System定義在它的specification中。
模型計算
P System的計算過程從開始狀態到終止態經歷了一系列的離散的步驟。每一步都涉及系統中所有膜結構和規則套用的疊代反應。這些步驟的執行遵循最大並行度和不確定性原則。隨著計算一步步的進行，當沒有任何進一步的反應能夠進行的時候，計算終止。此時被傳遞到環境中的那些物質被認為是計算的結果。
規則套用（Rule application）
計算的每一步每個物質都只能使用一次，因為它們會被套用的規則消耗掉。套用規則的方法如下：
● 從膜的內容中為規則的輸入指定物質。
● 如果所有輸入條件均滿足，從膜中移除指定過的物質。
● 創建輸出物質，並等待所有膜的所有規則的符號指定工作完成。
● 添加輸出物到目標膜。
● 分解膜（如果有必要的話）
輸出結果並不是立即傳遞到膜內，因為這可能會導致與規則套用的最大並行性產生矛盾。只有在所有可以套用的規則都已經被套用之後，才開始做輸出處理。
不確定性套用（Non-deterministic application）
規則套用的順序是隨機的。這個順序會產生顯著的效果，它會導致每一步產物的不同。
假設某層膜只包含一個單獨的符號“a”，和兩條規則：a → ab 和 a → aδ。這裡只有一個a，但是兩條規則都需要它，計算的第一步會使得兩者之一得以套用。所得到的結果也是非常不同的：
● 反應先得到ab，則會繼續對a發生隨機反應。
● 先套用a → aδ，則會使當前膜被分解並得到一個單獨的“a”符號。
最大並行套用（Maximally parallel application）
這是一個規則套用的屬性，也就是說每一個步驟中，所有規則的指派都必須得到充分實施。例如規則a → aa，意味著每一步中a的數量都會翻倍，因為規則被套用到每一個出現“a”符號的地方。
計算示例
右上方的圖描繪的是一個具有三層膜的P System的起始態。最外層膜（編號1）是容器膜，它只包含了一條out規則。2號膜包含了四條規則，其中有兩條規則之間有優先權關係。"δ"用來表示分解膜。3號膜包含了符號“ac”和三條here規則。因為1，2都缺少套用規則的必要符號，所以只能從3種的規則開始。
計算
由於P系統的不確定特性，上面這個例子有許多解的路徑，會得到不同的結果。下面我們來看看其中一種可能的解的途徑。
第一步
"c" 被指派給規則 c → cc
"a" 被指派給規則 a → ab
第二步
3號膜現在包含了: "abcc"
"a" 被指派給規則 a → bδ
"c" 被指派給規則 c → cc
"c" 被指派給規則 c → cc
第三步
2號膜現在包含了: “bbcccc”
"b" 被指派給規則 b → d
"b" 被指派給規則 b → d
"cc" 被指派給規則 cc → c
"cc" 被指派給規則 cc → c
第四步
2號膜現在包含了: "ddcc"
"d" 被指派給規則 d → de
"d" 被指派給規則 d → de
"cc" 被指派給規則 cc → c
第五步
2號膜現在包含了: “dedec”
"d" 被指派給規則 d → de
"d" 被指派給規則 d → de
"c" 被指派給規則 c → δ
注意這裡優先權雖然要cc→ c優先，但是已經不滿足其套用條件（缺少一個c），所以套用c → δ，2號膜現在被分解，所有包含的物質被傳遞給1號膜。
第六步
1號膜現在包含了: “deedee”
“e” 被指派給規則 e → eout
“e” 被指派給規則 e → eout
“e” 被指派給規則 e → eout
“e” 被指派給規則 e → eout
計算結束
1號膜現在包含了: "dd" 而環境包含了: "eeee." ，此時已經不能再進行任何規則指派。所以計算的結果就是“eeee”。僅有的不確定性選擇發生在前兩步中。
