Hispanopedia Wiki
Articulo de referencia

Sistema P

Para obtener información sobre el sistema informático p-System, consulte UCSD p-System . Un sistema P es un modelo computacional en el campo de la informática que realiza cálcul...

Hispanopedia WikiContenido en espanolLectura gratuita
Para obtener información sobre el sistema informático p-System, consulte UCSD p-System .

Un sistema P es un modelo computacional en el campo de la informática que realiza cálculos mediante un proceso de inspiración biológica. Se basa en la estructura de las células biológicas , abstraiendo 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 «Sistemas P». Las variaciones del modelo de sistema P dieron lugar a una rama de investigación conocida como « computación de membranas ».

Aunque inspirados 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 ]

Descripción informal

Un 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. Estas reglas también pueden provocar que las sustancias químicas atraviesen las membranas o incluso que estas se disuelvan .

Al igual que en una célula biológica, donde una reacción química solo puede ocurrir por casualidad, cuando las moléculas químicas necesarias colisionan e interactúan (posiblemente con un catalizador), las reglas en un sistema P se aplican aleatoriamente. Esto provoca que el cálculo se desarrolle de forma no determinista , lo que a menudo resulta en la obtención de múltiples soluciones si se repite el cálculo.

El sistema AP continúa hasta alcanzar un estado en el que no son posibles más reacciones. En este punto, el resultado del cálculo son todos los compuestos químicos que han pasado fuera de la membrana más externa, o bien aquellos que han pasado a una membrana de "resultado" designada. [ 4 ]

Componentes de un sistema P

Aunque existen muchas variantes del sistema P, la mayoría comparte los mismos componentes básicos. Cada elemento desempeña una función específica y tiene su origen en la arquitectura celular biológica sobre la que se fundamentan los sistemas P.

El medio ambiente

El entorno es el contexto del sistema P. En su estado inicial, el sistema P contiene únicamente la membrana contenedora, y si bien el entorno nunca puede contener reglas, puede recibir objetos durante el cálculo. Los objetos que se encuentran dentro del entorno al finalizar el cálculo constituyen la totalidad o parte de su "resultado".

Membranas

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, que se encuentra dentro del entorno, se suele denominar “membrana contenedora” o “membrana superficial”. Como su nombre indica, 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 hacia la membrana que lo contenía. [ 2 ]

Algunas variantes del sistema P permiten que una membrana se divida, posea una carga o tenga permeabilidad variable al cambiar el grosor de la membrana. [ 2 ]

Símbolos

Los símbolos representan sustancias químicas que pueden reaccionar con otras 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 simbólico de una membrana se representa mediante una cadena de letras. Dado que la multiplicidad de símbolos en una región es importante, se suelen utilizar multiconjuntos para representar el contenido simbólico de dicha región.

Existen símbolos para casos especiales; por ejemplo, la letra delta minúscula (δ) se usa a menudo para iniciar la disolución de una membrana, y esta solo se encontrará en el resultado de una regla: al ser encontrada, provoca una reacción y se utiliza en el proceso.

Catalizadores

Los catalizadores son similares a sus homólogos en química. Se representan y utilizan del mismo modo que los símbolos, pero nunca se consumen durante una reacción ; simplemente son un requisito para que esta se produzca.

Normas

Las reglas representan una posible reacción química dentro de una membrana, provocando su evolución hacia un nuevo estado. Cada regla requiere un conjunto de objetos de entrada (símbolos o catalizadores) que deben estar presentes para su aplicación. Si los objetos requeridos están presentes, la regla los consume y produce un conjunto de objetos de salida. También se puede especificar que una regla tenga prioridad sobre otras, en cuyo caso las reglas menos importantes solo se aplicarán cuando no sea posible aplicar una regla más importante (es decir, cuando no estén presentes los objetos de entrada requeridos).

En el modelo básico del sistema P, existen tres formas distintas en que una regla puede manejar sus objetos de salida. Generalmente, los objetos de salida se pasan a la membrana actual (la misma membrana donde residen la regla y las entradas), lo que se conoce como regla " aquí" . Sin embargo, al definir las reglas, se pueden especificar dos modificadores para los objetos de salida: ` in` y `out` . El modificador `in` hace que el objeto se pase a una de las membranas hijas de la membrana actual (en sentido interno con respecto a la estructura del sistema P), elegida aleatoriamente durante el cálculo. El modificador `out` hace que el objeto salga de la membrana actual y pase a su membrana padre o a una membrana hermana, especificada durante la definición del sistema P.

Proceso de cálculo

Un cálculo se realiza desde un estado inicial hacia un estado final mediante 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 cual ocurre de manera máximamente paralela y no determinista . [ 4 ]

Al seguir un proceso paso a paso, el cálculo se detiene cuando ya no puede haber más evolución (es decir, cuando no se pueden aplicar más reglas). En este punto, cualquier objeto que se haya pasado al entorno o a una membrana de "resultado" designada se considera el resultado del cálculo. [ 4 ]

Aplicación de la norma

En cada paso de un cálculo, un objeto solo puede usarse una vez, ya que las reglas los consumen al aplicarlos. El método para aplicar una regla dentro de una membrana es el siguiente:

  1. Asignar símbolos del contenido de una membrana a las entradas de la regla.
  2. Si se cumplen todas las condiciones de entrada, elimine todos los símbolos asignados de la membrana.
  3. Cree símbolos de salida y manténgalos en espera hasta que se haya realizado la asignación de reglas para todas las membranas.
  4. Agregue símbolos de salida a las membranas seleccionadas.
  5. Disuelva las membranas según sea necesario.

Los resultados no se transfieren inmediatamente a las membranas, ya que esto contravendría la naturaleza de máxima paralelización de la aplicación de reglas; en su lugar, se distribuyen después de que se hayan aplicado todas las reglas posibles.

Aplicación no determinista

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 qué reglas se aplican en un momento dado y en el resultado de cada paso de la ejecución.

Consideremos una membrana que contiene un único símbolo "a" y las dos reglas a → ab y a → aδ. Dado que 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:

  1. La membrana pasa al siguiente paso del cálculo con un símbolo "a" y un símbolo "b" presentes, y nuevamente una de las dos reglas se asigna aleatoriamente al símbolo "a".
  2. La membrana se disuelve y un único símbolo "a" pasa a la membrana contenedora.

Aplicación máximamente paralela

Esta es una propiedad de la aplicación de reglas según la cual todas las asignaciones de reglas posibles deben tener lugar en 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.

Como modelo computacional

La mayoría de las variantes de los sistemas P son computacionalmente universales . [ 4 ] Esto se extiende incluso a variantes que no utilizan prioridades de reglas, generalmente un aspecto fundamental de los sistemas P. [ 6 ]

Como modelo de computación, los sistemas P ofrecen la atractiva posibilidad de resolver problemas NP-completos en tiempo no 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 estos problemas. Como actualmente no existe un método para implementar directamente un sistema P, 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 ]

Ejemplo de cálculo

La representación gráfica de un sistema P que produce números cuadrados.

La imagen mostrada 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 asemejan a diagramas de Venn o al Higraph de David Harel (véase Statechart ).

La membrana más externa, 1, es la membrana contenedora para este sistema P y contiene una única regla de salida . La membrana 2 contiene cuatro reglas de aquí , con dos 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, ninguna regla fuera de la membrana 3 es aplicable: 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 en otras membranas se activarán.

Cálculo

Debido a la naturaleza no determinista de los sistemas P, un mismo sistema P puede realizar diversas rutas de cálculo, lo que conduce a resultados distintos. A continuación, se muestra una posible ruta de cálculo para el sistema P representado.

Paso 1

De la configuración inicial, solo la membrana 3 tiene algún contenido de objeto: "ac"

  • "c" se asigna a c → cc
  • "a" se asigna a a → ab

Paso 2

La membrana 3 ahora contiene: "abcc"

  • "a" se asigna a a → bδ
  • "c" se asigna a c → cc
  • "c" se asigna a c → cc

Observe el comportamiento de máxima paralelismo en la aplicación de reglas, lo que lleva a que la misma regla se aplique dos veces durante un mismo 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 puede considerarse aleatoria. El sistema podría haber seguido aplicando la primera regla (y, al mismo tiempo, duplicando las partículas c) indefinidamente.

La membrana 3 se disuelve ahora, 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.

Paso 3

La membrana 2 ahora contiene: " bbcccc "

  • "b" se asigna a b → d
  • "b" se asigna a b → d
  • "cc" se asigna a cc → c
  • "cc" se asigna a cc → c

Paso 4

La membrana 2 ahora contiene: " ddcc "

  • "d" se asigna a d → de
  • "d" se asigna a d → de
  • "cc" se asigna a cc → c

Paso 5

La membrana 2 ahora contiene: " dedec "

  • "d" se asigna a d → de
  • "d" se asigna a d → de
  • "c" se asigna a c → δ

Nótese que la prioridad sobre c → δ se ha eliminado, ya que las entradas necesarias para cc→ c ya no existen. La membrana 2 se disuelve y todo el contenido del objeto pasa a la membrana 1.

Paso 6

La membrana 1 ahora contiene: " deedee "

  • "e" se asigna a e → e fuera
  • "e" se asigna a e → e fuera
  • "e" se asigna a e → e fuera
  • "e" se asigna a e → e fuera

El cálculo se detiene.

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 asignar más objetos a las reglas. El resultado del cálculo son cuatro símbolos "e".

Las únicas decisiones no deterministas se produjeron durante los pasos 1 y 2, al elegir dónde asignar el símbolo "a". Consideremos el caso en el que "a" se asigna a a → bδ durante el paso 1: al disolverse la membrana 3, existirían solo un objeto "b" y dos objetos "c", lo que daría lugar a la creación de un único objeto "e" que finalmente se distribuiría como resultado del cálculo.

Véase también

Referencias

  1. ↑ Păun, Gheorghe (1998). Computing with Membranes . TUCS Report 208. Turku Centre for Computer Science. ISBN 978-952-12-0303-9Consultado el 16 de diciembre de 2012 .
  2. 1 2 3 4 Păun, Gheorghe ; Grzegorz Rozenberg (2002). "Una guía para la computación de membranas". Theoretical Computer Science . 287 (1): 73– 100. CiteSeerX 10.1.1.76.8425 . doi : 10.1016/S0304-3975(02)00136-6 . ISSN 0304-3975 .  
  3. ↑ Ardelean, Ioan; Matteo Cavaliere (junio de 2003). "Modelado de procesos biológicos mediante un software de sistema probabilístico p". Natural Computing . 2 (2): 173– 197. doi : 10.1023/A:1024943605864 . hdl : 11380/1321206 . ISSN 1567-7818 . 
  4. 1 2 3 4 5 6 Păun, Gheorghe (2006). «Introducción a la computación de membranas». Aplicaciones de la computación de membranas . Springer Berlin Heidelberg. págs. 1–42 . ISBN  978-3-540-29937-0.
  5. ↑ Nash, Anthony; Sara Kalvala (2019). "Modelo de sistema AP de enjambre y agregación en una colonia de mixobacterias" . Journal of Membrane Computing . 1 (2): 103– 11. doi : 10.1007/s41965-019-00015-0 .
  6. ↑ Freund, Rudolf; Kari, Lila; Oswald, Marion; Sosík, Petr (2005). "Sistemas P computacionalmente universales sin prioridades: dos catalizadores son suficientes". Theoretical Computer Science . 330 (2): 251– 266. doi : 10.1016/j.tcs.2004.06.029 . ISSN 0304-3975 . 
  7. ↑ Păun, Gheorghe (2001). "Sistemas P con membranas activas: abordando problemas NP-completos" (PDF) . Autómatas, lenguajes y combinatoria . 6 (1): 75– 90. Recuperado el 3 de febrero de 2008 .
  8. ↑ Zandron, Claudio; Claudio Ferretti; Giancarlo Mauri (2000). «Resolución de problemas NP-completos mediante sistemas P con membranas activas». Modelos no convencionales de computación . págs. 289–301 . ISBN  1-85233-415-0.
  • Sistemas P : sitio web para la investigación de sistemas P.