La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Archive for the ‘Calculabilidad’ Category

Gödel en una cáscara de nuez: La diagonalización de Cantor

Posted by Carlos en marzo 14, 2007

Cuando hace algunas semanas hablábamos de Gödel, surgió evidentemente el tema de sus Teoremas de Incompletitud, y su relación con la noción de computabilidad. Esta última es realmente interesante, y merece la pena detenerse un poco en ella. Para ello, quizás sea bueno hacer primero una pequeña introducción informal a los resultados de Gödel, ya que como apuntaba Alf en el hilo de discusión, están sumamente relacionados con dicha noción. De hecho, hay un elemento previo que -aumentando un poco el nivel de abstracción- podemos encontrar tanto en el trabajo de Gödel, como en el de Turing, entre otros muchos. Se trata del corte diagonal de Cantor.

El corte diagonal -o diagonalización- de Cantor es una de las más poderosas herramientas a las que podemos recurrir cuando razonamos con conjuntos infinitos. De hecho, una de sus primeras aplicaciones fue la demostración de que la infinitud de los números reales es mayor que la infinitud de los números naturales. La base del argumento -que se puede extender a conjuntos infinitos arbitrarios- es demostrar que es imposible definir una relación 1-a-1 entre los elementos de un conjunto y otro. Siguiendo el ejemplo anterior, supongamos que efectivamente podemos establecer una relación de ese tipo, es decir, que existe una función biyectiva

f:\mathbb N \longrightarrow \mathbb R.

Ahora demostraremos que tal función no existe, ya que hay al menos un número real r que no es imagen de ningún número natural. Para ello, definamos la función Di(s) como el dígito i-ésimo del número real s. Podemos entonces considerar un número real r, tal que

D_i(r) = (D_i(f(i))+1) \mod 10.

Claramente, no existe ningún número natural n tal que f(n) = r, ya que la imagen de cualquier valor n difiere de r en el dígito n-ésimo. De hecho, podemos ver cómo se obtiene una contradicción si se sustituye r por f(n) en la expresión de Dn(r):

D_n(r) = D_n(f(n)) = (D_n(f(n))+1) \mod 10.

Esto también se puede ver gráficamente si nos imaginamos una matriz en la que la fila i-ésima representa la lista (infinita) de dígitos del número real asociado al número natural i. El número r que hemos definido se obtiene tomando la diagonal de la matriz, y sumando 1 (módulo 10) a cada dígito, con lo que claramente difiere de todas las filas de la matriz. La función f no es por lo tanto suprayectiva, dado que hay más números reales que naturales.

El resultado anterior fue generalizado por el propio Cantor en el teorema que lleva su nombre, y que afirma que el conjunto potencia de un conjunto (es decir, el conjunto de todos los subconjuntos de uno dado) tiene más elementos que el conjunto base. Esto que es obvio para conjuntos finitos, no era trivial para conjuntos infinitos, pero puede demostrarse de acuerdo con el anterior razonamiento: supongamos que existe una función que relaciona elementos de un conjunto base infinito S con subconjuntos de elementos de dicho conjunto:

f: S \longrightarrow 2^S.

Podemos ahora definir un subconjunto

T=\{s\in S\ |\ s\notin f(s)\}

Supongamos que existe un t tal que f(t)= T. Preguntémonos ahora si t pertenece a T o no:

  • Si t pertenece a T, entonces t pertenece a f(t)=T, luego no cumple la condición necesaria para pertenecer a T.
  • Si t no pertenece a T, entonces no pertenece a f(t), lo que por definición hace que pertenezca a T.

En ambos casos llegamos a una contradicción, lo que implica que nuestra suposición de partida, esto es, que existía un t cuya imagen era T es falsa. Por lo tanto, la cardinalidad de 2S es mayor que la de S. El mismo razonamiento puede aplicarse a su vez al conjunto potencia de 2S, ad infinitum, lo que resulta en una jerarquía de números transfinitos. En el caso concreto de que S sea el conjunto de los números naturales, obtenemos la secuencia:

\aleph_0,\ c,\ 2^c,\ 2^{2^c},\ \cdots ,

donde \aleph_0 es la cardinalidad de los naturales, y c=2^{\aleph_0} es la cardinalidad de los números reales. Cantor dedicó infructuosamente mucho tiempo a intentar demostrar si c=\aleph_1 o no, esto es, si la cardinalidad de los reales es el primer número transfinito mayor que \aleph_0. Esto es lo que se conoce como la hipótesis del continuo, cuya versión generalizada es

|A|=\aleph_i \Leftrightarrow |2^A|=\aleph_{i+1}

donde |X| representa la cardinalidad de un conjunto X. Fue precisamente Gödel el que demostraría en 1940 (22 años tras la muerte de Cantor) la futilidad de intentar una demostración en el sistema axiomático ZFC (Zermelo-Fraenkel con Axioma de elección), ya que la hipótesis del continuo es independiente del mismo.

Una vez presentado el corte diagonal de Cantor, la siguiente parada en el camino son los teoremas de incompletitud de Gödel. El próximo día hablamos de ello.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

Posted in Calculabilidad, Matemáticas | 5 Comments »

Lo que la computación cuántica (no) puede hacer por nosotros

Posted by Carlos en febrero 13, 2007

Computador cuánticoHoy es el día en el que los muchachos de D-Wave planean hacer la presentación de su sistema cuántico Orión, tal como Alvy nos acaba de recordar en Microsiervos. Creo que puede ser entonces interesante analizar someramente qué es lo que la computación cuántica nos puede ofrecer, ya que se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas como las de Guti en el ámbito del mediocampo del Real Madrid. Para ponernos en situación, es necesario empezar por algunos preliminares que nos ayuden entender el nicho en el que los computadores cuánticos pueden ser útiles.

En primer lugar, vamos a comenzar por definir un marco computacional (puede hacerse una discusión en términos más abstractos, pero es más simple centrar las cosas en un modelo concreto). Hay diferentes posibilidades, pero vamos a ser clásicos e inclinarnos por las máquinas de Turing (MT). Una MT es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La MT se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q0, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.

Esta definición de MT es suficiente para abarcar cualquier algoritmo (de hecho un algoritmo se define como una MT). En particular, un algoritmo cuántico es simulable en una MT, por lo que un supuesto ordenador cuántico no nos va a permitir nada que no podamos hacer con nuestro PC, Mac, o -ya puestos- ZX-81. Por supuesto, es posible que -aunque no pueda hacer nada nuevo- un algoritmo cuántico sí pueda ser más eficiente que un algoritmo clásico. Nos adentramos entonces en los vericuetos de la complejidad computacional, y necesitamos definir algunos conceptos adicionales, empezando por el de MT no determinista (nMT).

Una nMT es una MT en la que la función de transición puede estar sobre- o sub-especificada, es decir, se puede indicar más de un comportamiento en una determinada situación o ninguno en absoluto. Lógicamente, lo primero es más interesante. Podemos imaginarnos que cuando se produce una de estas situaciones en la que la función de transición indica más de una posibilidad, la nMT se ramifica, produciendo copias de la máquina que exploran estas posibilidades en paralelo. Contrariamente a lo que una primera impresión pudiera hacer pensar, este paralelismo masivo no nos permite nuevamente hacer nada que no pueda hacer una MT determinista, pero sí que permite realizar una tarea mucho más deprisa (exponencialmente más rápido). Podemos emplear esta posibilidad para realizar una clasificación de los problemas computacionales de decisión (problemas para los que tenemos que encontrar una respuesta SÍ o NO) en dos clases: P y NP. La primera comprende aquellos problemas para los que una MT determinista puede encontrar la respuesta en un número polinomial (en el tamaño del problema) de pasos, es decir, en algo del orden de nc, donde n es dicho tamaño y c es una constante que no depende de n. Análogamente, NP es el conjunto de problemas de decisión para los que una nMT puede encontrar la respuesta en un número polinomial de pasos (es decir, basta con que una de las ramas encuentre la solución en tiempo polinomial). Hay numerosos problemas prácticos de optimización cuya versión decisional (e.g., la que tiene por respuesta SÍ o NO) está en la clase NP. Por ejemplo, el problema del viajante de comercio (TSP): dado un conjunto de ciudades, encontrar una ruta de longitud mínima que pase por todas las ciudades, sin repetir ninguna, y vuelva a la ciudad de partida. La versión decisional de este problema sería plantear: ¿existe un camino de las características requeridas cuya longitud sea inferior a K?

En relación al ejemplo anterior, no consta que el TSP (entre otros muchos problemas) esté en P, lo que hace plantearse la cuestión de si es que no se conoce aún un algoritmo polinomial para él, o es que realmente el problema es intrínsecamente no-polinomial. En otras palabras, dado que P está claramente contenida en NP (porque toda MT determinista es una nMT también), se ignora si la inclusión es estricta o no, esto es, si hay problemas en NP que no estén en P. Se cree que sí los hay, pero no hay demostración en un sentido o en otro (hay un premio de 1,000,000$ para quien lo consiga demostrar). Lo que sí se sabe es que o bien P = NP (en cuyo caso la necesidad de computadores cuánticos pasa a ser muy cuestionable), o bien hay tres tipos de problemas en NP: los problemas en P, y otros dos tipos que veremos a continuación, una vez se defina el concepto de completitud para una clase.

Se dice que un problema X es completo para la clase C, si X es un problema que pertenece a la clase C, y cualquier otro problema en C es reducible a X. A grandes rasgos, esto último quiere decir que dada una instancia de un problema Y perteneciente a C, podemos usar un cierto procedimiento R para convertirlo en una instancia del problema X. Si esto es así, X representa el mayor grado de dificultad dentro de la clase (cualquier otro problema es a lo sumo tan complejo de resolver como X). En el caso particular de NP requerimos que la transformación anterior se haga con un algoritmo polinomial. El problema de la satisfacibilidad es un problema completo para NP. Hay otros muchos que pueden consultarse aquí.

Bajo la suposición de que P no es igual a NP, los problemas NP-completos están lógicamente fuera de P, pero también hay problemas que ni están en P, ni son NP-completos. No consta que un algoritmo cuántico, gracias a la aceleración que el uso de estados superpuestos permita, pueda resolver en tiempo polinomial un problema NP-completo, y de hecho se piensa que no podrá. La utilidad de los computadores cuánticos será entonces para problemas no NP-completos como la factorización de enteros (una utilidad mucho más reducida de lo que los optimistas de D-Wave afirman). En otro artículo ya trataremos esto con más detalle, y lo cuantificaremos más formalmente. Vamos a esperar mientras tanto a ver en qué queda la presentación de Orión.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Calculabilidad, Complejidad, Matemáticas | Etiquetado: | 31 Comments »