| 词条 | P System |
| 释义 | P System （P系统）是一种仿生物技术的计算模型，它建立在生物细胞的结构基础之上，由细胞处理化学物质的机理抽象而来。P System的思想最初在1998年由罗马尼亚的计算机科学家Gheorghe Paun提出，P System正是由他的姓氏(Paun)而得名。之后，各类基于P System的模型层出不穷，导致了一个新的研究领域 - “膜计算”的诞生。 P System概述P System被定义为一系列包含化学物质（有限数量的），催化剂和规则（包括反应规则，膜运输规则等）的膜结构。 就像在真实的生物细胞里一样，化学反应只有在反应物相接触（有时会有催化剂）的时候才会发生，而由于P System的规则是随机应用的，这导致了计算结果的不确定性，换句话说，同一问题的重复的计算可能导致多个解决方案的产生。 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的计算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计算的示例右上方的图描绘的是一个具有三层膜的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”。仅有的不确定性选择发生在前两步中。 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。