Muchos problemas interesantes que se pueden resolver por medio de algoritmos en un determinado modelo precisan de un alto coste para su resolución, ya sea en tiempo y/o en espacio, siendo habitual que el intento de disminuir una de las dos medidas provoca un crecimiento exponencial en la otra. Por ello, surge la necesidad de buscar nuevos modelos que sean capaces de reducir ambos parámetros o, al menos, de incluir procedimientos en los que un coste alto en una de las medidas sea asimilado, en cierto sentido, por el propio modelo en beneficio de una reducción considerable sobre la otra.

En este contexto, la búsqueda de nuevos modelos alternativos de computación está encaminada a la mejora cuantitativa en los resultados que proporciona la Teoría de la Complejidad.

En los últimos años, esta búsqueda ha dado como resultado la introducción de nuevos modelos de computación sustancialmente distintos de los clásicos o convencionales (máquinas de Turing, funciones recursivas, Lambda-cálculo, máquinas URM, modelo GOTO, etc.) que proporcionan una mejora importante en las medidas de complejidad y en el marco de una posible implementación práctica.

La Computación Natural surge como una de las posibles alternativas a la computación que podríamos denominar clásica, en la búsqueda de nuevos paradigmas que puedan proporcionar una solución efectiva a las limitaciones que poseen los modelos convencionales. Actualmente, dentro del concepto de Computación Natural se engloba un conjunto de modelos que tienen como característica común la simulación del modo en que la naturaleza actúa/opera sobre la materia (hay quien extiende este concepto hasta abarcar modelos tales como la computación cuántica, que no se ajusta fielmente a la interpretación anterior). Es decir, la Computación Natural estudia la forma en que las diversas leyes de la naturaleza producen modificaciones en determinados sistemas (desde hábitats hasta conjuntos de moléculas, pasando por organismos vivos) que pueden ser interpretados como procesos de cálculo sobre sus elementos. Así, un hábitat en el que varias especies de seres vivos conviven, sufre transformaciones con el paso de las generaciones y en donde la interacción entre las especies puede provocar cambios en los elementos que la forman (cambios que pueden afectar desde la distribución de dichas especies en el hábitat hasta la morfología propia de cada especie). Es lo que entendemos como evolución de las especies; un conjunto de moléculas en un entorno con determinadas características (de temperatura, salinidad, etc) puede evolucionar hacia estados estructuralmente más complejos modificando las características de las mismas; es decir, propiciando reacciones químicas entre ellas que pueden llegar a producir elementos funcionalmente más complejos, como son las moléculas de ácido desoxirribonucléico (ADN).

Ahora bien: ¿qué entendemos por computación? ¿qué procesos pueden ser considerados como computaciones y cuáles no? ¿la Naturaleza produce computaciones? ¿a qué niveles? Si bien no podemos adentrarnos mucho a la hora de responder a estas cuestiones, sí hemos de precisar algunas cosas. Desde luego, la Naturaleza evoluciona, el fín primordial de la vida es la vida misma y la computación no es, propiamente, una actividad natural en tanto en cuanto sólo los humanos podemos etiquetar como computaciones ciertos procesos. Por ello, nosotros adoptaremos una perspectiva pragmática: entenderemos por computación todo aquello que puede ser simulado, de alguna manera, por una máquina de Turing; es decir, a partir de una cierta entrada se produce una salida a través de la ejecución de una serie de instrucciones u operaciones perfectamente definidas. Dos ingredientes básicos son necesarios en cualquier dispositivo computacional: una estructura de datos que proporcione los objetos sobre los que se trabaja, y una serie de operaciones o instrucciones que actúen sobre dichos objetos. Con estos elementos fundamentales aparecen de manera natural las computaciones: a partir de una situación inicial descrita por la configuración del dispositivo (donde se codifica el dato de entrada) y por la ejecución de una sucesión de instrucciones, se definen las sucesivas configuraciones obtenidas usando las operaciones de acuerdo con la semántica del modelo hasta llegar a una configuración exitosa que produce un dato de salida.

La simulación que aborda la Computación Natural puede tener diversas interpretaciones a la hora de describir los nuevos modelos: que se utilice para el diseño de nuevos esquemas algorítmicos usando técnicas inspiradas en la naturaleza, o bien que sugiera la creación física de nuevos modelos experimentales en los que el medio electrónico de los ordenadores convencionales se sustituya por otro sustrato que pueda implementar ciertos procesos que aparecen en el modo de operar de la Naturaleza.

Como ejemplo de la primera interpretación, podemos considerar los Algoritmos Genéticos (o de manera más general, la computación evolutiva), que se basan en el proceso genético de los seres vivos a través del cual evolucionan y cuyo elemento fundamental es el principio de selección natural, y las Redes Neuronales artificiales que están inspiradas en la organización y funcionamiento del cerebro (siendo el origen de los autómatas finitos). Tanto los Algoritmos Genéticos como las Redes Neuronales artificiales están inspiradas en la Biología y han sido implementadas en ordenadores electrónicos. Su estudio tiene como finalidad la obtención de nuevos tipos de algoritmos que permitan mejorar el rendimiento de las máquinas convencionales e incluso su propia arquitectura.

Como ejemplo de la segunda interpretación, a finales de la década de los cincuenta el premio nobel R.P. Feynman postula la necesidad de considerar operaciones sub-microscópicas como única alternativa revolucionaria en la carrera por la miniaturización de las componentes físicas de los ordenadores convencionales (basados en circuitos de silicio), y propone la computación a nivel molecular como posible modelo en el que implementar dichas operaciones. De esta manera, los complejos moleculares empiezan a ser considerados como componentes virtuales de un dispositivo de procesamiento de información. En 1987, T. Head propone explícitamente el primer modelo teórico molecular basándose en las propiedades de la molécula de ADN. En noviembre de 1994, L. Adleman realiza el primer experimento en un laboratorio que permite resolver una instancia concreta de un problema NP-completo a través de la manipulación de moléculas de ADN.

Computación Molecular

Como ya se ha comentado, a finales de la década de los cincuenta, el premio nobel R.P. Feynman describe los ordenadores sub-microscópicos e introduce el concepto teórico de computación a nivel molecular, postulándolo como una innovación necesaria y revolucionaria en la carrera por la miniaturización. Las ideas de Feynman adquieren una especial relevancia a partir de 1983, cuando R. Churchhouse establece las limitaciones físicas de la velocidad de cálculo de un procesador convencional, demostrando que, bajo los principios de la física, existe una cota para la velocidad y el tamaño que los microprocesadores pueden alcanzar. Esta cota, además, impediría resolver con las técnicas actuales problemas que en la actualidad se consideran intratables, por precisar un tiempo muy elevado para resolver ejemplares de tamaño relativamente grande, imponiendo que por mucho que aceleremos los microprocesadores (incluso alcanzando dicha cota física) seguiríamos teniendo instancias de esos problemas que precisarían años o siglos para poder resolverlos en esas supermáquinas.

En 1987, T. Head propone el primer modelo computacional abstracto basado en la manipulación de las moléculas de ADN, el modelo splicing. En este modelo la información es almacenada en cadenas de caracteres al modo en que lo hacen las moléculas de ADN, y las operaciones que se pueden realizar sobre dichas cadenas son similares a las que realizan ciertas enzimas sobre el ADN.

L.M. Adleman materializa esta similitud en noviembre de 1994 mostrando que es posible usar procesos biológicos para atacar la resolubilidad de instancias de ciertos problemas matemáticos especialmente difíciles: mediante un experimento realizado en el laboratorio consiguió resolver una instancia concreta de un problema computacionalmente intratable usando técnicas de biología molecular para la manipulación del ADN. Aunque el experimento de Adleman no es propiamente una implementación práctica del modelo que diseñó T. Head, el tipo de sustrato utilizado (moléculas de ADN) así como las operaciones que usa sobre dicho sustrato son similares a las propuestas por el modelo splicing.

• En julio de 2000, un equipo de científicos de la Universidad de California desarrolló un interruptor del tamaño de una millonésima de milímetro (un nanómetro), a partir de una molécula. Todo parece indicar que este interruptor puede representar una alternativa revolucionaria en relación con los actuales chips de silicio.
• En su funcionamiento sustituye la electricidad por una reacción química, lo que representa un importante ahorro en el consumo de energía.
• Estos nuevos interruptores podrían disponer de más de mil procesadores en el espacio ocupado hoy día por un sólo procesador (los actuales chips de silicio tienen una altura aproximada de cinco mil nanómetros).
• Se estima que estos interruptores podrían aumentar la velocidad de procesamiento de la información cien mil millones de veces la de un ordenador convencional, y podrían reproducir la capacidad equivalente a cien ordenadores convencionales en el tamaño de un grano de sal fina.

En la actualidad han surgido modelos moleculares alternativos al propuesto por T. Head. Algunos de esos modelos utilizan el ADN como molécula básica y la diferencia entre dichos modelos estriba en las distintas operaciones que se consideran primitivas o elementales. Otros modelos utilizan diferentes tipos de moléculas biológicas como dispositivo para almacenar la información (como el ARN) y enzimas específicas para su tratamiento. Ahora bien, todos esos modelos tienen como denominador común el uso de moléculas estructuralmente complejas que han demostrado su eficacia en la naturaleza, tanto en el almacenamiento de información como en la diversidad y potencia de las operaciones que se pueden realizar sobre ellas.

Los modelos moleculares constituyen una rama de la Computación en la que intervienen áreas del conocimiento humano muy distintas y, tradicionalmente, disjuntas, que van desde las disciplinas más abstractas de las matemáticas hasta las aplicaciones más novedosas que se puedan obtener en los laboratorios de biología molecular. Esta característica hace que muchos de los avances en la creación de modelos eficientes pase ineludiblemente por la consecución de nuevas, eficientes y robustas técnicas de manipulación de las moléculas con las que se trabaja en el laboratorio.

Computación celular con Membranas

Hasta ahora hemos hablado de modelos de computación natural en los que se simula el modo en que la naturaleza calcula a un nivel genético (computación molecular basada en ADN), y en a literatura se ha considerado también a un nivel neuronal (redes neuronales). Un estudio más detallado del funcionamiento de los organismos vivos nos sugiere un nuevo nivel de computación no analizado hasta ahora: el nivel celular.

El comportamiento de una célula puede ser considerado como el de una máquina que realiza un cierto proceso de cálculo: una máquina no trivial, desde el punto de vista biológico, en la que por medio de una distribución jerárquica de membranas interiores se produce el flujo y alteración de las componentes químicas que la propia célula procesa.

Por supuesto, los procesos que se producen en una célula son lo suficientemente complejos como para que sea imposible modelizarlos completamente ya que un modelo de computación que intente simular literalmente esos procesos dejaría de ser práctico, salvo desde un punto de vista biológico. Con este tipo de computación, se pretende crear un modelo de computación abstracto que simule, de la forma más aproximada posible, el comportamiento de las células y que nos permita (al menos en principio) obtener soluciones alternativas de problemas computacionalmente intratables desde un punto de vista convencional. Para ello, hay que hacer emerger todas aquellas características del comportamiento y constitución de la célula que puedan ser de utilidad para la elaboración de un modelo de computación que sea a la vez potente (en cuanto a los problemas que pueda resolver) y sencillo (en cuanto a su definición, implementación y ejecución).

La primera característica que llama la atención en cuanto a la estructura interna de la célula, es el hecho de que las distintas partes del sistema biológico que la componen se encuentran delimitadas por varios tipos de membranas (en su sentido más amplio), desde la propia membrana que separa el exterior de la célula del interior de la misma, hasta las distintas membranas que delimitan las vesículas interiores. Además, con respecto a la funcionalidad de estas membranas en la naturaleza, interesa el hecho de que no generan compartimentos estancos sino que permiten el paso (flujo) de ciertos compuestos químicos, algunas veces de forma selectiva e incluso en una sola de las direcciones. Estas ideas han sido consideradas con anterioridad por G. Berry y V. Manca independientemente.

Fig. 1: Una estructura de membranas con las regiones delimitadas

En las células tienen lugar una serie de reacciones químicas que provocan una transformación de las componentes químicas presentes en sus membranas, junto con un flujo de las mismas entre los distintos compartimentos que la integran. Estos procesos a nivel celular pueden ser interpretados como procedimientos de cálculo.

La Computación celular con Membranas ha sido hasta ahora el último modelo de Computación Natural. Fue introducido por Gh. Paun en octubre 1998 como un modelo de tipo distribuido y paralelo, y está inspirado en el funcionamiento de la célula como organismo vivo capaz de procesar y generar información.

Los ingredientes básicos de un P sistema (que es como también se conocen los sistemas que utilizan la computación celular con membranas) son la estructura de membranas, que consiste en un conjunto de membranas (al modo de las vesículas que componen las células) incluidas en una piel exterior que las separa del entorno, junto con ciertos multiconjuntos de objetos (es decir, conjuntos en los que los elementos pueden aparecer repetidos) situados en las regiones que delimitan dichas membranas (al modo de los compuestos que hay en el interior de dichas vesículas). Estos objetos pueden transformarse de acuerdo con unas reglas de evolución que son aplicadas de una forma no determinista, paralela y maximal (al modo de las reacciones que se pueden producir entre dichos compuestos). Para simular la permeabilidad de las membranas celulares, las reglas de evolución no sólo pueden modificar los objetos presentes en una membrana, sino que pueden pasar a través de dos regiones adyacentes atravesando la membrana que las separa.

Fig. 2: Un P sistema que calcula los cuadrados de números naturales

Este modelo de computación implementa un paralelismo masivo en dos niveles básicos: en un primer nivel, cada membrana aplica sus reglas de forma paralela sobre los objetos presentes en ella, produciendo los nuevos objetos y comunicándolos a las membranas adyacentes si procediera; en un segundo nivel, todas las membranas realizan esta operación en paralelo, trabajando simultáneamente, sin interferencia alguna de las operaciones que se estén produciendo en las demás membranas del sistema.

A pesar de que el modelo de computación celular tiene inspiración biológica, puede resaltarse el hecho de que constituye igualmente un buen modelo teórico de computación distribuida, en donde distintas unidades de cálculo trabajan independientemente pero estructuradas en una cierta jerarquía vertical; por ejemplo, la jerarquización usada en las conexiones establecidas en redes como internet puede ser representada como una estructura de membranas.

Nota: Extraído del capítulo 3 del libro "Máquinas moleculares basadas en ADN", de Mario de J. Pérez Jiménez y Fernando Sancho Caparrini