Pシステム

コンピュータ p-System については、UCSD p-System を参照してください。

Pシステムは、生物学にヒントを得たプロセスを使用して計算を実行するコンピュータサイエンスの分野における計算モデルです。生物細胞の構造に基づいており、化学物質が相互作用して細胞膜を通過する方法を抽象化しています。この概念は、コンピュータ科学者のGheorghe Păunによる1998年のレポート^{[1]で初めて導入されました。Pシステムの}Pは、彼の姓が由来です。Pシステムモデルのバリエーションにより、「膜コンピューティング」と呼ばれる研究分野が形成されました。

Pシステムは生物学に触発されたものの、主な研究対象は生物学的モデリングではなく計算モデルとしての利用である^[2]。ただし、これも研究されている。^{[3] [4] [5]}

AP システムは、化学物質 (有限量)、触媒、および化学物質が互いに反応して生成物を形成する可能性のある方法を決定する規則を含む一連の膜として定義されます。規則によって化学物質が膜を通過したり、膜が溶解したりすることもあります。

生物細胞では、必要な化学分子が衝突して相互作用する（場合によっては触媒も）という偶然の出来事によってのみ化学反応が起こる可能性があるのと同様に、P システムのルールはランダムに適用されます。これにより、計算は非決定論的に進行し、計算を繰り返すと複数の解に遭遇することがよくあります。

APシステムは、それ以上の反応が不可能な状態に達するまで継続します。この時点で、計算の結果は、最外膜の外側を通過したすべての化学物質、または指定された「結果」膜を通過したすべての化学物質です。^[4]

P システムにはさまざまな種類がありますが、そのほとんどは同じ基本コンポーネントを共有しています。各要素には特定の役割があり、それぞれが P システムの基盤となる生物学的細胞構造に根ざしています。

環境とは、P システムの周囲のことです。P システムの初期状態では、環境にはコンテナー膜のみが含まれます。環境はルールを保持することはできませんが、計算中にオブジェクトが渡されることがあります。計算の終了時に環境内で見つかったオブジェクトは、その「結果」のすべてまたは一部を構成します。

膜は P システム内の主要な「構造」です。膜は、一連のオブジェクト (シンボル/触媒)、一連のルール、および内部に含まれる他の一連の膜を含むことができる個別のユニットです。環境内に保持される最も外側の膜は、「コンテナ膜」または「スキン膜」と呼ばれることがよくあります。名前が示すように、膜は透過性があり、ルールから生じるシンボルは膜を通過できます。膜 (コンテナ膜は除く) は「溶解」する可能性があり、その場合、その内容は、ルール (失われます) を除いて、それが含まれた膜に移動します。^[2]

いくつかのPシステムの変異体は、膜が分裂したり、電荷を持ったり、膜の厚さを変えることで透過性を変化させたりすることを可能にする。^[2]

シンボルは、他の化学物質と反応して何らかの生成物を形成する可能性のある化学物質を表します。P システムでは、各タイプのシンボルは通常、異なる文字で表されます。したがって、膜のシンボル コンテンツは文字列で表されます。領域内のシンボルの多重度が重要であるため、領域のシンボル コンテンツを表すには、通常、マルチセットが使用されます。

特殊なケースのシンボルが存在します。たとえば、小文字のデルタ(δ) は膜の溶解を開始するためによく使用され、ルールの出力でのみ使用されます。デルタが検出されると、反応が呼び出され、プロセスで使用されます。

触媒は化学における同名の物質に似ています。記号と同じように表現され、使用されますが、「反応」中に消費されることはなく、単に反応を起こすために必要なものにすぎません。

ルールは膜内で起こり得る化学反応を表し、膜を新しい状態に進化させます。ルールには、適用するために存在しなければならない入力オブジェクト (シンボルまたは触媒) の必須セットがあります。必須オブジェクトが存在する場合、ルールはそれらを消費し、出力オブジェクトのセットを生成します。ルールは他のルールよりも優先されるように指定することもできます。その場合、より優位なルールを適用できない (つまり、必要な入力が存在しない) 場合にのみ、より優位性の低いルールが適用されます。

ルールが出力オブジェクトを処理する方法は 3 つあります (基本的な P システム モデルの場合)。通常、出力オブジェクトは現在のメンブレン (ルールと入力が存在するのと同じメンブレン) に渡されます。これはhereルールと呼ばれます。ただし、ルールを定義するときに出力オブジェクトに指定できる修飾子が 2 つあります。in修飾子は、計算中にランダムに選択された現在のメンブレンの子 (P システムの構造に対して内側に移動する) の 1 つにオブジェクトを渡します。 out修飾子は、オブジェクトを現在のメンブレンから渡して、P システムの指定中に指定された親メンブレンまたは兄弟メンブレンのいずれかに渡します。

計算は、いくつかの離散的なステップを経て、初期の開始状態から終了状態に向かって行われます。各ステップでは、Pシステム内のすべての膜を反復処理し、ルールを適用します。これは、最大限に並列かつ非決定的な方法で行われます。^[4]

ステップごとに計算を進めていくと、それ以上の進化が起こらなくなったとき（つまり、ルールを適用できなくなったとき）に計算は停止します。この時点で、環境に渡されたオブジェクト、または指定された「結果」膜に渡されたオブジェクトはすべて、計算の結果としてカウントされます。^[4]

計算の各ステップでは、オブジェクトは適用時にルールによって消費されるため、1 回しか使用できません。メンブレン内でルールを適用する方法は次のとおりです。

1. 膜の内容からシンボルをルールの入力に割り当てる
2. すべての入力が満たされた場合、割り当てられたすべてのシンボルを膜から削除します。
3. 出力シンボルを作成し、すべての膜に対してすべてのルールの割り当てが行われるまで保持します。
4. ターゲット膜に出力シンボルを追加します。
5. 必要に応じて膜を溶解する

出力は、ルール適用の最大並列性に反するため、すぐに膜に渡されるのではなく、すべての可能なルールが適用された後に配布されます。

ルールの適用順序はランダムに選択されます。ルールの適用順序は、特定の時点で適用されるルールや実行ステップの結果に大きな影響を与える可能性があります。

膜に「a」記号が 1 つだけ含まれていて、a → ab と a → aδ という 2 つの規則があるとします。どちらの規則も「a」記号が存在することを前提としていますが、そのような記号は 1 つしかありません。そのため、計算の最初のステップでは、最初の規則と 2 番目の規則のいずれかが適用されますが、両方は適用されません。このステップで起こり得る 2 つの結果は大きく異なります。

1. 膜は、「a」記号と「b」記号の両方が存在する状態で計算の次のステップに引き継がれ、再び 2 つのルールのうちの 1 つが「a」記号にランダムに割り当てられます。
2. 膜が溶解し、単一の「a」記号がそれを含む膜に渡されます。

これは、ルール適用の特性であり、計算の各ステップですべての可能なルール割り当てを実行する必要があります。本質的には、ルール a → aa は、ルールが存在するすべての「a」シンボルに適用されるので、各ステップでその包含膜内の「a」シンボルの数を 2 倍にする効果があることを意味します。

Pシステムのバリアントのほとんどは計算上普遍的です。^[4]これは、通常Pシステムの基本的な側面であるルールの優先順位を使用しないバリアントにまで及びます。^[6]

計算モデルとして、PシステムはNP完全問題を指数時間未満で解く魅力的な可能性を提供します。^[4] Pシステムのいくつかのバリアントは、SAT（ブール充足可能性）問題を線形時間で解くことができることが知られており^[7]、すべてのNP完全問題は同等であるため、この機能はそのようなすべての問題に適用されます。現在、Pシステム自体を直接実装する方法はないため、代わりにその機能がエミュレートされ^{[8] 、したがってNP完全問題を線形時間で解くことは理論上のもののままです。ただし、決定論的なPシステムは}チューリングマシンで多項式時間でシミュレートできることも証明されています。^[2]

示されている画像は、3 つの膜を持つ P システムの初期状態を表しています。P システムは階層的な性質を持つため、ベン図やDavid HarelのHigraph ( Statechart を参照) に似た図でグラフィカルに表現されることがよくあります。

最も外側の膜 1 は、この P システムのコンテナ膜であり、単一のoutルールが含まれています。膜 2 には 4 つのhereルールが含まれており、そのうち 2 つは優先関係にあります。cc → c は、常に c → δ よりも優先して適用されます。デルタ記号は、特別な「溶解」記号を表します。最も内側の膜 3 には、一連の記号 (“ac”) と、タイプhereの 3 つのルールが含まれています。この初期状態では、膜 3 の外側のルールは適用できません。つまり、その膜の外側には記号がありません。ただし、システムの進化の過程で、オブジェクトが膜間を通過されると、他の膜のルールがアクティブになります。

P システムの非決定論的性質のため、単一の P システムで実行できる計算パスは多数あり、異なる結果をもたらします。以下は、図に示す P システムの計算パスの 1 つです。

初期構成では、膜3にのみオブジェクトコンテンツ「ac」があります。

• 「c」はcに割り当てられる → cc
• 「a」はaに割り当てられる → ab

膜 3 には現在「abcc」が含まれています。

• 「a」はa→bδに割り当てられる
• 「c」はcに割り当てられる → cc
• 「c」はcに割り当てられる → cc

ルール適用の最大並列動作により、1 つのステップで同じルールが 2 回適用されることに注意してください。

また、最初のルール (a → ab) ではなく 2 番目のルール (a → bδ) の適用は非決定論的であり、ランダムであると想定できることにも注意してください。システムは、最初のルール (および同時に c 粒子を 2 倍にする) を無期限に適用し続けることもできたでしょう。

溶解記号 (δ) に遭遇したため、膜 3 は溶解し、この膜のすべてのオブジェクト コンテンツは膜 2 に渡されます。

メンブレン 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 → δに割り当てられます

c → δ の優先順位が解除され、cc→ c に必要な入力がなくなったことに注意してください。膜 2 は溶解し、すべてのオブジェクトの内容が膜 1 に渡されます。

膜 1 には現在、「deedee」が含まれています。

• 「e」はeに割り当てられる → e _out
• 「e」はeに割り当てられる → e _out
• 「e」はeに割り当てられる → e _out
• 「e」はeに割り当てられる → e _out

_{メンブレン 1 には「dd」が含まれ、アウト ルール e → e out}により、環境には「eeee」が含まれます。この時点で、ルールへのオブジェクトの割り当てがこれ以上できなくなるため、計算は停止します。計算の結果は、4 つの「e」シンボルになります。

唯一の非決定論的な選択は、ステップ 1 と 2 で、単独の「a」シンボルをどこに割り当てるかを選択するときに発生しました。ステップ 1 で「a」が a → bδ に割り当てられる場合を考えてみましょう。膜 3 が溶解すると、1 つの「b」オブジェクトと 2 つの「c」オブジェクトのみが存在するため、計算の結果として最終的に渡される 1 つの「e」オブジェクトのみが作成されます。

• 細胞（生物学）
• 生物学にヒントを得たコンピューティング
• 正式な言語
• ハイパーグラフ
• MG 1000
• システム生物学

• P システム – P システム研究の Web サイト。