La computación de membrana (o MC ) es un área dentro de la informática que busca descubrir nuevos modelos computacionales a partir del estudio de células biológicas , particularmente de las membranas celulares . Es una subtarea de crear un modelo celular .
La computación de membrana se ocupa de modelos de computación distribuidos y paralelos, procesando conjuntos múltiples de objetos de símbolo de manera localizada. Por tanto, las reglas de evolución permiten encapsular los objetos en evolución en compartimentos definidos por membranas. Las comunicaciones entre compartimentos y con el medio ambiente juegan un papel fundamental en los procesos. Los diversos tipos de sistemas de membranas se conocen como sistemas P en honor a Gheorghe Păun, quien concibió el modelo por primera vez en 1998. [1]
Un ingrediente esencial de un sistema P es su estructura de membrana, que puede ser una disposición jerárquica de membranas, como en una célula, o una red de membranas (colocadas en los nodos de un gráfico), como en un tejido o una red neuronal. Los sistemas P a menudo se representan gráficamente con dibujos.
La intuición detrás de la noción de membrana es una vesícula tridimensional de la biología. Sin embargo, el concepto en sí es más general y una membrana se ve como un separador de dos regiones. La membrana proporciona una comunicación selectiva entre las dos regiones. Según Gheorghe Păun, la separación es del espacio euclidiano en un "interior" finito y un "exterior" infinito. La comunicación selectiva es donde entra en juego la informática.
Las representaciones gráficas pueden tener numerosos elementos, según la variación del modelo que se esté estudiando. Por ejemplo, una regla puede producir el símbolo especial δ, en cuyo caso la membrana que la contiene se disuelve y todo su contenido se mueve hacia arriba en la jerarquía de la región.
La variedad de sugerencias de la biología y la gama de posibilidades para definir la arquitectura y el funcionamiento de un dispositivo de procesamiento multiset basado en membranas son prácticamente infinitas. De hecho, la literatura sobre computación de membranas contiene una gran cantidad de modelos. Por lo tanto, MC no es simplemente una teoría relacionada con un modelo específico, es un marco para diseñar modelos compartimentados.
Los productos químicos se modelan mediante símbolos o, alternativamente, mediante cadenas de símbolos. La región, que está definida por una membrana, puede contener otros símbolos o cadenas (denominados colectivamente objetos) u otras membranas, de modo que un sistema P tiene exactamente una membrana externa, llamada membrana de la piel, y una relación jerárquica que gobierna todas sus membranas. membranas debajo de la membrana de la piel.
Si los objetos son símbolos, entonces importa su multiplicidad dentro de una región; sin embargo, en algunos modelos de cuerdas también se utilizan conjuntos múltiples. Las regiones tienen reglas asociadas que definen cómo se producen, consumen, pasan los objetos a otras regiones y cómo interactúan entre sí. La aplicación no determinista de reglas en paralelo máximo en todo el sistema es una transición entre estados del sistema, y una secuencia de transiciones se denomina cálculo. Se pueden definir objetivos particulares para indicar un estado de detención, en cuyo punto el resultado del cálculo serían los objetos contenidos en una región en particular. Alternativamente, el resultado puede estar formado por objetos enviados al medio ambiente desde la membrana de la piel.
Se han estudiado muchos modelos variantes y el interés se ha centrado en demostrar la universalidad computacional para sistemas con un número reducido de membranas, con el fin de resolver problemas NP-completos como los problemas de satisfacibilidad booleana (SAT) y el problema del viajante de comercio (TSP) . Los sistemas P pueden cambiar las complejidades del espacio y el tiempo y, con menos frecuencia, utilizan modelos para explicar los procesos naturales en las células vivas. Los estudios diseñan modelos que, al menos teóricamente, pueden implementarse en hardware. Hasta la fecha, los sistemas P son casi todos modelos teóricos que nunca se han reducido a la práctica, aunque se da un sistema práctico. [2]
Ver también
Referencias
- ↑ Păun, Gheorghe. "Introducción a la computación de membranas" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Patente de EE. UU. 20,090,124,506