Menú

    Enlaces...

  • No es la primera vez que me he topado con alguien que piensa que la ciencia es una cuestión de creencias u opiniones o que el término “Teoría” en ciencia tiene asociado el mismo concepto que cuando usamos la palabra para para definir algo dudoso. A todos ellos les terminé explicando algo parecido a lo que dice Ivan K. Schuller al respecto. [Via]:La media hostia # (1)

La paradoja de Hawking

1 de julio de 2007

Estoy de vuelta… al menos por un tiempo. Y vuelvo para hablaros de un documental que me ha gustado mucho: La paradoja de Hawking (click para ver el documental. Me encanta stage6), un análisis sobre la contradicción que Hawking nos mostró cuando formuló su teoría sobre los agujeros negros.

Agujero NegroComo definición de cafetería, podemos llamar agujero negro a un cuerpo de densidad enorme, o lo que es lo mismo, un cuerpo con una masa muy grande en proporción a su tamaño. Esta concentración de masa produce tal campo gravitatorio que ni tan siquiera las partículas de luz escapan. De ahí su nombre. La creación de éstos tiene lugar cuando una estrella del orden mínimo de 2.5 veces el tamaño del sol se colapsa.

El documental habla de cómo las investigaciones de Hawking (mucho más genio para mí ahora que empiezo a entender las implicaciones de sus descubrimientos) le llevaron a deducir la estructura de un agujero negro. Pero además, le llevaron a demostrar que la materia que absorbe un agujero negro acaba desapareciendo, desvaneciéndose. Y esto choca de lleno con uno de los principios fundamentales de la física, que nos dice que la materia no se destruye, poniendo en entredicho los pilares de la física y el método científico, pues es la causa-efecto la que ayuda a los científicos a determinar el pasado y predecir el futuro. Si esa materia simplemente dejara de existir no podríamos prever lo siguiente que ocurriría.

Pero la historia acaba feliz. Tampoco quiero destriparos el documental entero, además de que no estoy yo tan ducho en este tema como para hablar con propiedad. Las pocas cosas que sé de esto tema las aprendí precisamente del best-seller de Hawking, Breve Historia del Tiempo, en su nueva edición reducida y revisada, Brevísima Historia Del Tiempo, que MrWolf y Nkn me regalaron hace un par de años, y en la que ya aparecen referencias a la Teoría de Cuerdas. Pero eso es ya otra historia de la que quizás algún día me atreva a escribir.

Enlaces relacionados:

Máquinas inspiradas en la naturaleza viva (II)

4 de abril de 2007

Atención: Esta anotación es la continuación de Máquinas inspiradas en la naturaleza viva (I)

Hace algunas semanas estuve escribiendo un poco acerca de la problemática actual en la computación, las limitaciones de los ordenadores tradicionales y la necesidad de superar esas limitaciones para resolver problemas de la vida real. Como decía, la existencia de problemas NP-Completos que no son posibles de resolver en tiempo polinomial en una computadora convencional, ha llevado a los investigadores a diseñar nuevos modelos de computación que en un futuro puedan superar estas barreras de eficiencia. Muchos de vosotros seguramente habrá leído sobre la computación cuántica y cómo con ella se ha consigue (teóricamente) romper algunas claves de encriptación.
Efectivamente, la computación cuántica es un modelo de computación no convencional. Sin embargo, yo quería hablar otros dos modelos, menos conocidos, que entran dentro de la denominada Computación Natural: La Computación Molecular basada en ADN (Adleman, 1994) y la Computación con Membranas (Gh. Paun, 1998).

Computación Molecular basada en ADN

En 1953 James Watson y Francis Crick presentaron su modelo de ADN de doble hélice. En él se describía la composición de los cromosomas como una doble hélice, donde cada una de ellas estaba a su vez compuesta por una cadena de aminoácidos. Este estudio les supuso el Premio Nobel.

ADN40 años después, Leonard Adleman, inventor de la criptografía RSA de la que hablábamos un poco en artículo anterior, estaba leyéndose el trabajo de estos dos físicos. Observó que en la mitosis de la célula, cuando se produce la replicación del ADN, interviene una enzima, la polimerasa. Al fijarse en cómo esta enzima creaba una copia perfecta de la información genética, se maravilló con el parecido que tenía ésta en su forma de actuar con una máquina de Turing de doble cinta (estas cosas siempre me hacen pensar en si las matemáticas se inventan o se descubren…). Inmediatamente se puso a trabajar en la elaboración de un experimento que utilizara el ADN para realizar cálculos computacionales. En 1994 publicaría este experimiento en una revista científica (la revista Science, creo), en el que resolvía una instancia del problema del Camino Hamiltoniano (un problema NP-Completo) con 7 vértices. Hay que aclarar que tanto el problema como la solución se encontraban codificados apropiadamente en cadenas de ADN, donde el alfabeto está formado por las posibles bases nitrogenadas: Adenina, Citosina, Timina y Guanina.
¿Cómo es posible construir un modelo computacional basado en ADN? Bueno, si nos abstraemos lo suficiente podemos llegar a ver que para construir un modelo computacional necesitamos dos cosas: Un soporte para almacenar información y la posibilidad de realizar operaciones sobre esa información. Y esto es lo que Adleman descubrió y aprovechó para construir su modelo, formado principalmente por tubos (recipientes) que contenían multiconjuntos de agregados (datos), y las operaciones de extraer de un tubo, meclar dos tubos y detectar alguna sustancia en un tubo. Con este modelo, su experimento consistió, resumiendo mucho, en:

  1. Generar aleatoreamente el conjunto de secuencias de vértices, donde cada una es un posible camino.
  2. Eliminar, por filtrado, las codificaciones que no correspondan con los caminos que empiecen y acaben por los vértices de los que parte el problema
  3. Eliminar, también por filtrado, todas las secuencias no compuestas por los n vértices del grafo.
  4. Eiminar todas las secuencias que contengan algún vértice repetido.
  5. Si el tubo final, resultado de todos los filtrados anteriores, sigue conteniendo secuencias de ADN, devolver sí. En caso contrario, devolver no.

Y bueno, por último, quería contar qué es lo que cambia en este modelo con respecto a un modelo de computación tradicional: La clave está en el paralelismo masivo. El hecho de que en un tubo se estén realizando millones de operaciones simultáneas por segundo, hace posible que problemas NP-Completos se puedan resolver en tiempos polinomiales. Es por ello que la computación basada en ADN haya tenido tanto éxito, porque constituye una huída hacia adelante en la investigación para la resolución de problemas de la vida real que con máquinas convencionales no pueden ser resueltos.

Continuará…

Máquinas inspiradas en la naturaleza viva (I)

21 de marzo de 2007

Detrás del título de esta conferencia que impartió Mario de J. Pérez Jiménez el miércoles 7 de marzo, nos encontramos con uno de los aspectos más apasionantes de la computación. Y si además quien habla de ello es este profesor del departamento de Ciencias de la Computación e Inteligencia Artificial mucho mejor. Tuve el honor de tenerlo en la asignatura Computabilidad y Complejidad el pasado cuatrimestre y verdaderamente es un hombre que contagia su ímpetu y sus ganas de aprender y seguir investigando. Su conferencia, sobre computación natural, fue densa, llena de conceptos, pero todo ello necesario para comprender en qué consiste su actual línea de investigación.

Y es que estamos hablando del que sea posiblemente el problema matemático más importante del milenio: La conjetura P=NP. De hecho, este problema es el primero de la lista que el Instituto Clay de Matemáticas (Cambridge, Massachusetts) elaboró, premiando con un millón de dólares a aquél que sea capaz de resolver alguno de ellos. Como curiosidad, tan sólo uno ha sido resuelto por ahora, la conjetura de Poincaré (ahora ya teorema), hace sólo algunos meses. Pero cuando la conjetura P=NP está la primera en la lista es sin duda por algo. Y es que la demostración de ésta llevaría consigo muchísimas cosas, y entre ellas la posibilidad de resolver los 5 restantes problemas.

¿Pero en qué consiste esta igualdad? ¿Qué es P y qué es NP?

Bueno, ambas son clases de complejidad, es decir, conjuntos de problemas de decisión (con decisión me refiero a que su solución es una afirmación o una negación, un o un no, un 1 ó un 0) que guardan unas propiedades comunes:

  • La Clase P es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista (o el equivalente a un ordenador convencional) en tiempo polinomial. Lo de determinista quiere decir que a valores iguales de entrada, el resultado siempre será el mismo. Esto es fácil de entender si alguna vez has hecho una función o un método en algún lenguaje de programación. Si llamas 2 veces a alguna de tus funciones con los mismos argumentos de entrada, el resultado será el mismo.
  • La Clase NP es el conjunto de problemas resolubles por una máquina de Turing no determinista en tiempo polinomial. Una máquina de Túring no determinista es áquella que posee varias computaciones diferentes para una misma entrada.

Hay que aclarar que la potencia de una MTD es la misma que la de una MTND. Ambas son capaces de resolver los mismos problemas. Su diferencia reside en la eficiencia. Y esta eficiencia es la que trae de cabeza a todos los investigadores, pues hay algunos problemas, los de mayor complejidad de la clase NP (los llamados problemas NP-Completos), que al intentar resolverlos con ordenadores convencionales tardan un tiempo exponencial en función del tamaño de la entrada.
Un ejemplo de este tipo de problemas lo encontramos en el Problema del Viajante. En él, un viajante intenta visitar una serie de ciudades conectadas entre sí (imagínense un grafo donde los vértices son las ciudades y las aristas un camino entre dos ciudades) sin pasar 2 veces por ninguna, visitándolas todas y terminando en la ciudad de partida, siendo mínima la distancia recorrida por éste. Si aumentamos el tamaño del grafo (el número de ciudades) el tiempo que tardará un ordenador en resolver el problema, por muy rápido que sea, aumentará exponencialmente, de modo que para valores no muy altos de entrada no hay computadora capaz de devolver una solución.

¿Por qué es tan importante la conjetura P=NP?

Los algoritmos criptográficos, que hacen que la información viaje segura y que nadie no autorizado pueda acceder a cierta información se basan precisamente en el largo tiempo que una máquina tarda en descifrar las claves. Por ejemplo, la seguridad del sistema de encriptación RSA se basa en la imposibilidad de que una máquina tradicional factorice un número grande en factores primos en un tiempo decente. De esta manera la clave de descifrado se mantiene segura.
Pero si la conjetura P=NP fuera cierta, entonces sería posible diseñar un algoritmo que hiciera esto en tiempo polinomial. Hablando claro, podríamos diseñar un decodificador universal, capaz de descifrar cualquier tipo de mensaje encriptado. Además, muchos problemas de la vida real que actualmente no tienen solución por encontrarse frenados por un problema NP-Completo podrían ser resueltos. Los avances en la ciencia serían inimaginables.
Desafortunadamente, aunque aún no está demostrado, todo parece indicar que P es distinto de NP. Si esto es así, el mundo de la computación tal y como la conocemos tiene los días contados. La necesidad de buscar solución a muchos grandes problemas de la vida real ha llevado a crear nuevos modelos de computación alternativos, que se alejan del circuito electrónico que conduce pulsos eléctricos…

Continuará…

La deconstrucción del cerebro digital

12 de marzo de 2007

El viernes terminó Imaginática 2007. A mí personalmente me ha dejado muy buen sabor de boca. He asistido a conferencias muy interesantes y he conocido algunas muy buenas ideas, que abren puertas a la innovación tecnológica y esperanza en algunos campos de las TIC que actualmente se encuentran en crisis.

Manera en que los recuerdos se guardan en el cerebro, por capas, según su nivel de detalleUna de las conferencias que me gustó fue la que el grupo Digital Neuroscience Team dio el lunes 5. Titulada La deconstrucción del cerebro digital, la charla fue una conferencia densa en la que se dio una pequeña introducción a los nuevos caminos que se están abriendo para hacer que la mal llamada “Inteligencia Artificial” sea real algún día. Concretamente, se habló de HTM, un nuevo modelo de Aprendizaje Automático que revolucionará este campo y que se basa en simular la manera en que nuestro cerebro maneja nuestra memoria: “Si queremos crear máquinas que piensen como los humanos, empecemos por copiar la forma en que nuestro cerebro almacena los recuerdos y traslademos este algoritmo a una máquina electrónica…”

Un tema muy apasionante del que soy totalmente desconocedor, y quizás sea por eso que mi reacción sea un poco escéptica. Copiar un cerebro siempre ha sido para mí algo del futuro, donde los coches levitan y se supera la velocidad de la luz. No obstante, siempre hay que animar estas innovadoras ideas. Los más grandes avances siempre han sido los más controvertidos.
En resumen, una muy interesante conferencia. Felicito a los ponentes (algunos de ellos todavía alumnos de la escuela) por tan amena charla.

Enlaces Relacionados: