Un sistema P es un modelo computacional en el campo de la informática que realiza cálculos utilizando un proceso de inspiración biológica. Se basan en la estructura de las células biológicas , sin tener en cuenta la forma en que las sustancias químicas interactúan y atraviesan las membranas celulares . El concepto fue introducido por primera vez en un informe de 1998 [1] por el informático Gheorghe Păun , cuyo apellido es el origen de la letra P en 'P Systems'. Las variaciones del modelo del sistema P llevaron a la formación de una rama de investigación conocida como " computación de membrana ".
Aunque está inspirado en la biología, el principal interés de la investigación en los sistemas P se centra en su uso como modelo computacional, más que para el modelado biológico , [2] aunque esto también se está investigando. [3] [4] [5]
El sistema AP se define como una serie de membranas que contienen sustancias químicas (en cantidades finitas), catalizadores y reglas que determinan las posibles formas en que las sustancias químicas pueden reaccionar entre sí para formar productos. Las reglas también pueden hacer que las sustancias químicas atraviesen las membranas o incluso que las membranas se disuelvan .
Al igual que en una célula biológica, donde una reacción química sólo puede tener lugar si las moléculas químicas requeridas chocan e interactúan (posiblemente también con un catalizador), las reglas en un sistema P se aplican al azar. Esto hace que el cálculo se realice de manera no determinista , lo que a menudo da como resultado que se encuentren múltiples soluciones si se repite el cálculo.
El sistema AP continúa hasta que alcanza un estado en el que no son posibles más reacciones. En este punto, el resultado del cálculo son todas aquellas sustancias químicas que han pasado fuera de la membrana más externa o, de lo contrario, aquellas que han pasado a una membrana de "resultado" designada. [4]
Aunque existen muchas variedades de sistemas P, la mayoría comparte los mismos componentes básicos. Cada elemento tiene un papel específico que desempeñar y cada uno tiene una base en la arquitectura biológica de la célula en la que se basan los sistemas P.
El entorno es el entorno del sistema P. En el estado inicial de un sistema P, contiene sólo la membrana contenedora, y aunque el entorno nunca puede contener reglas, es posible que se le pasen objetos durante el cálculo. Los objetos encontrados dentro del entorno al final del cálculo constituyen todo o parte de su "resultado".
Las membranas son las principales "estructuras" dentro de un sistema P. Una membrana es una unidad discreta que puede contener un conjunto de objetos (símbolos/catalizadores), un conjunto de reglas y un conjunto de otras membranas contenidas en su interior. La membrana más externa, mantenida dentro del entorno, a menudo se denomina "membrana contenedora" o "membrana cutánea". Como lo indica su homónimo, las membranas son permeables y los símbolos resultantes de una regla pueden atravesarlas. Una membrana (pero no la membrana del contenedor) también puede “disolverse”, en cuyo caso su contenido, salvo reglas (que se pierden), migra a la membrana en la que estaba contenido. [2]
Algunas variantes del sistema P permiten que una membrana se divida, posea una carga o tenga una permeabilidad variable al cambiar el espesor de la membrana. [2]
Los símbolos representan sustancias químicas que pueden reaccionar con otras sustancias químicas para formar algún producto. En un sistema P, cada tipo de símbolo suele estar representado por una letra diferente. Por tanto, el contenido simbólico de una membrana se representa mediante una cadena de letras. Debido a que la multiplicidad de símbolos en una región es importante, comúnmente se usan conjuntos múltiples para representar el contenido de símbolos de una región.
Existen símbolos de casos especiales, por ejemplo, un delta minúsculo (δ) a menudo se usa para iniciar la disolución de una membrana, y esto solo se encontrará en el resultado de una regla: al encontrarse, invoca una reacción y se utilizado en el proceso.
Los catalizadores son similares a sus homónimos en química. Se representan y utilizan de la misma manera que los símbolos, pero nunca se consumen durante una “ reacción ”, simplemente son un requisito para que esta ocurra.
Las reglas representan una posible reacción química dentro de una membrana, lo que hace que evolucione a un nuevo estado. Una regla tiene un conjunto requerido de objetos de entrada (símbolos o catalizadores) que deben estar presentes para que se aplique. Si los objetos requeridos están presentes, los consume y produce un conjunto de objetos de salida. También se puede especificar que una regla tenga prioridad sobre otras reglas, en cuyo caso las reglas menos dominantes sólo se aplicarán cuando no sea posible aplicar una regla más dominante (es decir, los insumos requeridos no están presentes).
Hay tres formas distintas (en el modelo básico del sistema P) en las que una regla puede manejar sus objetos de salida. Por lo general, los objetos de salida pasan a la membrana actual (la misma membrana en la que residen la regla y las entradas), conocida como regla aquí . Sin embargo, hay dos modificadores que se pueden especificar en los objetos de salida cuando se definen reglas, dentro y fuera . El modificador in hace que el objeto pase a uno de los hijos de la membrana actual (que viaja hacia adentro en relación con la estructura del sistema P), elegido al azar durante el cálculo. El modificador de salida hace que el objeto salga de la membrana actual y entre en su membrana principal o en una membrana hermana, especificada durante la especificación del sistema P.
Un cálculo funciona desde un estado inicial inicial hacia un estado final a través de una serie de pasos discretos. Cada paso implica iterar a través de todas las membranas del sistema P y la aplicación de reglas, lo que ocurre de manera paralela al máximo y no determinista . [4]
Trabajando paso a paso, un cálculo se detiene cuando ya no puede haber más evolución (es decir, cuando no se pueden aplicar reglas). En este punto, cualquier objeto que haya pasado al medio ambiente o a una membrana de "resultado" designada se cuenta como resultado del cálculo. [4]
En cada paso de un cálculo, un objeto solo se puede usar una vez, ya que las reglas lo consumen cuando se aplican. El método para aplicar una regla dentro de una membrana es el siguiente:
Las salidas no pasan inmediatamente a las membranas porque esto contravendría la naturaleza paralela máxima de la aplicación de reglas, sino que se distribuyen después de que se hayan aplicado todas las reglas posibles.
El orden de aplicación de las reglas se elige al azar. El orden de aplicación de las reglas puede tener un efecto significativo sobre qué reglas se pueden aplicar en un momento dado y sobre el resultado de un paso de ejecución.
Considere una membrana que contiene solo un símbolo "a" y las dos reglas a → ab y a → aδ. Como ambas reglas dependen de la presencia de un símbolo "a", del cual solo hay uno, el primer paso del cálculo permitirá aplicar la primera o la segunda regla, pero no ambas. Los dos posibles resultados de este paso son muy diferentes:
Esta es una propiedad de la aplicación de reglas por la cual todas las posibles asignaciones de reglas deben tener lugar durante cada paso del cálculo. En esencia, esto significa que la regla a → aa tiene el efecto de duplicar el número de símbolos "a" en su membrana contenedora en cada paso, porque la regla se aplica a cada aparición de un símbolo "a" presente.
La mayoría de las variantes de los sistemas P son computacionalmente universales . [4] Esto se extiende incluso para incluir variantes que no utilizan prioridades de reglas, generalmente un aspecto fundamental de los sistemas P. [6]
Como modelo de cálculo, los sistemas P ofrecen la atractiva posibilidad de resolver problemas NP-completos en un tiempo menor que exponencial . [4] Se sabe que algunas variantes del sistema P son capaces de resolver el problema SAT (satisfacibilidad booleana) en tiempo lineal [7] y, debido a que todos los problemas NP-completos son equivalentes , esta capacidad se aplica a todos esos problemas. Como no existe un método actual para implementar directamente un sistema P por derecho propio, su funcionalidad se emula [8] y, por lo tanto, la resolución de problemas NP-completos en tiempo lineal sigue siendo teórica. Sin embargo, también se ha demostrado que cualquier sistema P determinista puede simularse en una máquina de Turing en tiempo polinomial . [2]
La imagen mostrada muestra el estado inicial de un sistema P con tres membranas. Debido a su naturaleza jerárquica, los sistemas P a menudo se representan gráficamente con dibujos que se parecen a los diagramas de Venn o al Higraph de David Harel (ver Statechart ).
La membrana más externa, 1, es la membrana contenedora de este sistema P y contiene una única regla de salida . La membrana 2 contiene cuatro reglas aquí , dos de las cuales están en una relación de prioridad: cc → c siempre se aplicará con preferencia a c → δ. El símbolo delta representa el símbolo especial de "disolver". La membrana más interna, 3, contiene un conjunto de símbolos (“ac”) y tres reglas, del tipo aquí . En este estado inicial no se aplican reglas fuera de la membrana 3: no hay símbolos fuera de esa membrana. Sin embargo, durante la evolución del sistema, a medida que los objetos pasan entre membranas, las reglas de otras membranas se activarán.
Debido a la naturaleza no determinista de los sistemas P, existen muchos caminos diferentes de cálculo que un solo sistema P es capaz de realizar, lo que conduce a diferentes resultados. La siguiente es una posible ruta de cálculo para el sistema P representado.
Desde la configuración inicial sólo la membrana 3 tiene algún contenido de objeto: "ac"
La membrana 3 ahora contiene: "abcc"
Observe el comportamiento máximo paralelo de la aplicación de reglas que lleva a que la misma regla se aplique dos veces durante un paso.
Observe también que la aplicación de la segunda regla (a → bδ) en contraposición a la primera (a → ab) no es determinista y se puede suponer aleatoria. El sistema también podría haber seguido aplicando la primera regla (y al mismo tiempo duplicando las partículas c) indefinidamente.
La membrana 3 ahora se disuelve, ya que se ha encontrado el símbolo de disolución (δ) y todo el contenido del objeto de esta membrana pasa a la membrana 2.
La membrana 2 ahora contiene: "bbcccc"
La membrana 2 ahora contiene: "ddcc"
La membrana 2 ahora contiene: "dedec"
Observe que la prioridad sobre c → δ se ha eliminado ahora que las entradas requeridas para cc → c ya no existen. La membrana 2 ahora se disuelve y todo el contenido del objeto pasa a la membrana 1.
La membrana 1 ahora contiene: "deedee"
La membrana 1 ahora contiene: "dd" y, debido a la regla de salida e → e out , el entorno contiene: "eeee". En este punto, el cálculo se detiene porque no es posible realizar más asignaciones de objetos a reglas. El resultado del cálculo son cuatro símbolos "e".
Las únicas elecciones no deterministas ocurrieron durante los pasos 1 y 2, al elegir dónde asignar el símbolo solitario "a". Considere el caso en el que "a" se asigna a a → bδ durante el paso 1: al disolverse la membrana 3, solo existirían un único objeto "b" y dos "c", lo que llevaría a la creación de un solo objeto "e" para eventualmente se distribuirá como resultado del cálculo.