Research Group on Natural Computing

El presente libro consta de tres capítulos, cada uno de los cuales desarrolla un tema específico relativo a un modelo de computación no convencional. Sus autores son Daniel Díaz Pernil, Juan Antonio Nepomuceno Chamorro y Antonio Jesús Ramos Espina, y los contenidos de cada uno de los capítulos se corresponden con el trabajo de investigación que cada uno de ellos ha presentado para la obtención de los 12 créditos de la fase de investigación del Programa de Doctorado Lógica, Computación e Inteligencia Artificial, adscrito al Departamento de Ciencias de la Computación e Inteligencia Artificial de la Universidad de Sevilla

El primer capítulo se titula Combinatoria en modelos moleculares sin memoria basados en ADN. Aplicaciones, y el objetivo fundamental es el desarrollo de una teoría de la combinatoria en modelos moleculares sin memoria basados en ADN, y su aplicación a la resolución eficiente de problemas NP-completos en dicho marco computacional.

En el segundo capítulo se presenta una introducción bastante completa a la Computación Cuántica, desde el análisis de las ideas que subyacen en el modelo, hasta la exposición de ejemplos que ilustren su funcionamiento, pasando por una exhaustiva exposición de los elementos básicos de la mecánica cuántica que son necesarios para comprender el nuevo modelo.

En el tercer capítulo se aborda un tema especialmente interesante de los modelos celulares con membranas; concretamente el uso de recursos precomputados a la hora de obtener buenas soluciones de problemas presuntamente intratables desde el punto de vista de la Complejidad Computacional clásica. En este capítulo se presenta un primer sistema celular que usa recursos precomputados, siguiendo las ideas de E. Czeiler, se estudia dicho modelo como un dispositivo reconocedor de lenguajes, y se describen soluciones de dos problemas de decisión (el test de primalidad y el problema de la satisfactibilidad de la lógica proposicional) en este nuevo marco.

Este libro debe ser considerado como una nueva aportación al estudio de los modelos de computación no convencionales. A menos que se pruebe la igualdad de las clases de complejidad P y NP, estos modelos constituyen hoy día una alternativa indispensable a los modelos convencionales cuya implementación ordinaria está basada en la manipulación electrónica del silicio, debido a las limitaciones físicas que tienen estos dispositivos.