Un sistema P es un modelo computacional en el campo de la ciencia 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 , haciendo abstracción de 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 científico informático Gheorghe Păun , cuyo apellido es el origen de la letra P en "P Systems". Las variaciones en el modelo del sistema P llevaron a la formación de una rama de investigación conocida como " computación de membrana ".
Aunque se inspira en la biología, el principal interés de investigación en los sistemas P se centra en su uso como modelo computacional, más que en 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 pasen a través de las membranas o incluso hacer que las membranas se disuelvan .
Al igual que en una célula biológica, donde una reacción química solo puede tener lugar si las moléculas químicas requeridas colisionan 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 PA 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 todos los productos químicos que han pasado fuera de la membrana más externa o, en su defecto, los que han pasado a una membrana "resultante" designada. [4]
Aunque existen muchas variedades de sistemas P, la mayoría comparte los mismos componentes básicos. Cada elemento tiene una función específica que desempeñar y cada uno tiene un fundamento en la arquitectura celular biológica en la que se basan los sistemas P.
El entorno es el entorno del sistema P. En el estado inicial de un sistema P, este contiene únicamente la membrana contenedora y, si bien el entorno nunca puede contener reglas, puede recibir objetos durante el cómputo. Los objetos que se encuentran dentro del entorno al final del cómputo constituyen todo o parte de su “resultado”.
Las membranas son las “estructuras” principales 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, contenida en el entorno, a menudo se denomina “membrana contenedora” o “membrana de la piel”. Como lo implica su nombre, las membranas son permeables y los símbolos resultantes de una regla pueden atravesarlas. Una membrana (pero no la membrana contenedora) también puede “disolverse”, en cuyo caso su contenido, excepto las 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 se representa normalmente con una letra diferente. Por lo tanto, el contenido de símbolos de una membrana se representa mediante una cadena de letras. Debido a que la multiplicidad de símbolos en una región es importante, los multiconjuntos se utilizan comúnmente para representar el contenido de símbolos de una región.
Existen símbolos de casos especiales, por ejemplo, a menudo se utiliza una delta minúscula (δ) para iniciar la disolución de una membrana, y esto solo se encontrará en el resultado de una regla: al encontrarlo, invoca una reacción y se utiliza en el proceso.
Los catalizadores son similares a sus homónimos en química. Se representan y se utilizan de la misma manera que los símbolos, pero nunca se consumen durante una “ reacción ”, simplemente son un requisito para que esta se produzca.
Las reglas representan una posible reacción química dentro de una membrana, 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 pueda aplicar. 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 solo se aplicarán cuando no sea posible aplicar una regla más dominante (es decir, las entradas requeridas no estén presentes).
Existen 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 se pasan a la membrana actual (la misma membrana en la que residen la regla y las entradas), conocida como regla here . Sin embargo, hay dos modificadores que se pueden especificar en los objetos de salida cuando se definen las reglas, in y out . El modificador in hace que el objeto se 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 out hace que el objeto se pase fuera de la membrana actual y hacia su membrana principal o hacia una membrana hermana, especificada durante la especificación del sistema P.
Un cálculo parte de un estado inicial y avanza hacia un estado final a través de una serie de pasos discretos. Cada paso implica la iteración a través de todas las membranas del sistema P y la aplicación de reglas, lo que ocurre de manera paralela y no determinista . [4]
Si se trabaja paso a paso, el cálculo se detiene cuando ya no es posible seguir evolucionando (es decir, cuando no es posible aplicar ninguna regla). En este punto, todos los objetos que se han pasado al entorno o a una membrana de "resultado" designada se cuentan como resultado del cálculo. [4]
En cada paso de un cálculo, un objeto solo se puede utilizar una vez, ya que las reglas lo consumen cuando se aplica. El método para aplicar una regla dentro de una membrana es el siguiente:
Los resultados no pasan inmediatamente a las membranas porque esto contravendría la naturaleza máximamente paralela 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 en las reglas que se pueden aplicar en un momento determinado y en el resultado de un paso de la ejecución.
Consideremos una membrana que contiene un solo símbolo "a" y las dos reglas a → ab y a → aδ. Como ambas reglas dependen de la presencia de un símbolo "a", de los cuales solo hay uno, el primer paso del cálculo permitirá aplicar la primera o la segunda regla, pero no ambas. Los dos resultados posibles de este paso son muy diferentes:
Esta es una propiedad de la aplicación de reglas según la cual todas las asignaciones de reglas posibles deben tener lugar durante cada paso del cálculo. En esencia, esto significa que la regla a → aa tiene el efecto de duplicar la cantidad de símbolos "a" en la membrana que la contiene en cada paso, porque la regla se aplica a cada ocurrencia 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 el exponencial . [4] Se sabe que algunas variantes de sistemas 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 actualmente no existe un método para implementar directamente un sistema P por derecho propio, su funcionalidad se emula en su lugar [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 que se muestra representa el estado inicial de un sistema P con tres membranas. Debido a su naturaleza jerárquica, los sistemas P suelen representarse gráficamente con dibujos que se parecen a los diagramas de Venn o al Higraph de David Harel (véase Diagrama de estados ).
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 de aquí , dos de ellas 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, de 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 muchas rutas de cálculo diferentes que un solo sistema P puede seguir, lo que conduce a diferentes resultados. La siguiente es una ruta de cálculo posible para el sistema P representado.
De la configuración inicial solo 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.
Obsérvese 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 presumir que es aleatoria. El sistema podría haber seguido aplicando la primera regla (y al mismo tiempo duplicar 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 se ha eliminado la prioridad sobre c → δ, ya 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 ya que no es posible realizar más asignaciones de objetos a las reglas. El resultado del cálculo son cuatro símbolos "e".
Las únicas elecciones no deterministas se dieron durante los pasos 1 y 2, al elegir dónde asignar el símbolo "a" solitario. 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 único objeto "e" que finalmente se transmitiría como resultado del cálculo.