A la página principal

puntitogris.gif (801 bytes)

Opinión        Libros y Revistas         Agenda        Documentos

puntitogris.gif (801 bytes)

PUBLICACIONES

Breviario

Cable Semanal

Educyt

Exactamente

Lista Exactas

MicroSemanario

Buscador
powered by FreeFind


Búsqueda Local
Búsqueda Web

Míercoles 3 de marzo de 2004

La información y el azar
Números casuales

El azar, ese fenómeno elusivo que caracteriza ciertos eventos -como por ejemplo nuestra propia existencia-, ha comenzado a ofrecer jugosos frutos para la teoría matemática y las ciencias de la computación. Aquí, una recorrida por el mundo de lo aleatorio.

Por Verónica Engler (*)

  Para habitués de casinos y apostadores de toda laya, sería una bendición poder encontrar un método que permitiera configurar la martingala ganadora en cada ocasión. Pero ese procedimiento, lamentablemente, no existe.

  En los juegos de azar, la experiencia y el tesón con que se observen las sucesivas secuencias de eventos no aportan ningún tipo de conocimiento útil para predecir desenlaces. No importa cuánto tiempo permanezca una persona observando girar la rueda de la ruleta y anotando afanosamente cada uno de los resultados. Aunque preste atención a todas las cifras aparecidas, el timbero empedernido no podrá hallar ningún patrón a partir del cual inferir en qué número caerá la bolilla cada vez.

  El de la ruleta es uno de esos fenómenos que se pueden observar sin entender lo que pasa ni adivinar lo que sucederá. Justamente eso es lo que se denomina azar: aquello que no se puede predecir, que puede suceder o no.

  Este fenómeno elusivo, que aparece como la antípoda de la certidumbre, en las últimas décadas ha comenzado a dar frutos jugosos para la teoría matemática y las ciencias de la computación.

  "Recién en los años 60 se consiguió formalizar una definición matemática del azar, fue dada al mismo tiempo por dos investigadores: uno fue Per Martin Löf, un discípulo de Andrei Kolmogorov (uno de los teóricos más importantes de la Teoría de las Probabilidades), y el otro fue un investigador que se llama Gregory Chaitin", relata Verónica Becher, doctora en Ciencias de la Computación y profesora de la materia Información y Azar en la Facultad de Ciencias Exactas y Naturales (FCEyN) de la UBA.

  Aunque Martin Löf y Chaitin llegaron al resultado por caminos diferentes, se demostró que las definiciones de ambos son equivalentes. La propuesta por Chaitin dice que una secuencia de dígitos es aleatoria cuando ninguno de los segmentos que uno elija como inicial se puede resumir mediante una descripción matemática. "Es decir, cuando cada uno de estos segmentos requiera un programa de computadora que los genere, cuya longitud será, al menos, tan larga como el segmento mismo, porque cada una de estas secuencias de símbolos iniciales no responde a una ley general", explica Becher, que trabaja junto a Chaitin (ver "El padre de Omega") desde hace varios años.

  Según esta definición, es factible comprobar la aleatoriedad de una secuencia de elementos si, fraccionándola arbitrariamente en segmentos, no se puede hallar en ninguna de estas porciones un patrón que regule la aparición de cada uno de los elementos. No importa en qué lugar de la secuencia se decida comenzar el escrutinio, cualquiera puede ser el segmento inicial. Examinar la secuencia a partir de las partes que la componen permite verificar la inexistencia de regularidades. Por ejemplo, si observáramos la lista de números que nuestro empedernido timbero registró durante un año, podríamos tomar segmentos de 5, 34, o 259 cifras a partir del primer día, del segundo mes, o del último bimestre del año en cuestión. No habrá, en ninguno de estos segmentos, un orden que contenga algún tipo de regularidad.

  Por eso mismo, las computadoras, tal como las conocemos, son incapaces de generar números verdaderamente aleatorios (del mismo tipo que los obtenidos con la ruleta). Como las acciones que pueden llevar a cabo ya están inscriptas en algún programa, las serviles máquinas sólo se encargan de cumplir órdenes: pura obediencia debida.

  De esta manera, si se quisieran guardar en una computadora diez millones de cifras que no siguen ningún patrón, solamente se podrá hacerlo ingresando trabajosamente cada uno de los elementos de esta secuencia: no existe ningún programa que permita economizar tiempo o espacio. Es decir, no hay una descripción matemática -algoritmo- de esa acción que pueda ser más breve que la producción de cada uno de los símbolos individualmente.

  En cambio, si cada uno de los diez millones de elementos fuera, por ejemplo, el número tres, sí se podría resumir muy fácilmente esa secuencia dando la instrucción de «imprimir diez millones de veces el número tres». La complejidad de la información de ambas secuencias es muy distinta. Justamente, la teoría de Chaitin se ocupa de esas diferencias. Desde esta perspectiva, la complejidad de la información es la longitud de la descripción más corta de una cadena de datos. Siguiendo esta definición, la secuencia de diez millones de cifras aleatorias es muy compleja, dado que requiere, por lo menos, diez millones de elementos para ser descripta. Diferente es el caso de los diez millones de 3: con sólo 39 elementos (letras) se podría compendiar esa serie numérica.

Esos raros números

  Para la mayoría de los mortales, los números no son más que unos grafismos útiles para contar los haberes y las deudas, o para cifrar el tiempo. Los usamos para sumar las adquisiciones y restar los gastos, para contabilizar los días y las ovejas que se suceden en nuestra imaginación mientras intentamos dormir. Pero ese conjunto de símbolos al que usualmente atamos algunas certezas no es más que una ínfima parte del universo numérico, quizás la menos interesante desde el punto de vista matemático.

  Los números irracionales (como la raíz cuadrada de dos), por ejemplo, conforman una clase de elementos bastante habitual en el infinito océano de los guarismos posibles, aunque estén prácticamente ausentes en las cuentas del día a día -para las que nos conformamos con los más predecibles números naturales-.

  Pensando en la rica variedad de fenómenos que escenifican los números, hace poco más de un siglo el matemático George Cantor sorprendió a colegas y pensadores de disímiles áreas del conocimiento con su Aleph, ese número que hacía añicos la concepción que hasta ese momento se tenía del infinito -entendido como la sucesión sin fin de los puntos de una recta correspondientes a valores enteros y racionales- y que afirmaba la existencia de múltiples dimensiones numéricas sin fin.

  Por lo visto, hay cifras que tienen la apariencia de lo imposible, y que vienen a postular mundos extrañamente inasibles. Un ejemplo de este tipo es Omega, un número aleatorio que halló Chaitin para definir la probabilidad de que una computadora, al correr un programa cualquiera, se detenga, es decir, complete totalmente la tarea que estaba realizando. "Para cada programa hay dos posibilidades cuando se ejecuta en la computadora: o bien realiza las acciones necesarias para finalizar la tarea programada y termina, o bien entra en un ciclo infinito, y por lo tanto no termina. No es predecible cuál de estas dos posibilidades ocurrirá". Estas dos opciones que destaca Becher definen un tópico altamente estudiado en las ciencias de la computación, es el problema de la detención: una incertidumbre a la que nos enfrentamos, sin saberlo, cada vez que ponemos a funcionar una computadora.

  Omega puede ser definido pero no exhibido, nunca se dejará ver como un resultado cuantificable, sino como una serie de ecuaciones y demostraciones matemáticas que dan cuenta de su ausencia. Esta entelequia numérica puede ser una atractiva puerta de entrada para investigar fenómenos que no se ciñen a la medida de la certeza.

  Este número aleatorio no es calculable, porque no puede ser predecible ni resumible (no se puede acotar en una secuencia más corta que el número mismo). Por contraste, podría pensarse en Pi, un extraño número que representa la relación entre la longitud de la circunferencia de un círculo y su diámetro. Generalmente representamos a Pi con el valor 3,14, aunque tiene muchas, muchísimas cifras decimales que pueden ser exhibidas: prueba de ello son los cálculos realizados con supercomputadoras que, a la fecha, han sacado a la luz más de 51 mil millones de decimales (!). Pero este no es el caso de Omega, "aunque no es calculable, se pueden realizar aproximaciones. Entonces se puede saber: ´Omega es más grande que esto´, ´es más grande que esto otro´ -describe Becher-. En sucesivos pasos algorítmicos, se va consiguiendo dar cotas para Omega, pero nunca se sabe cuán cerca se está de haber conseguido los dígitos más significativos".

  Siguiendo la ruta del azar, Becher continuó con los esfuerzos de Chaitin y demostró que no sólo existe el Omega normal, sino que hay Hiperomegas que también tienen su equivalente en el mundo real: pueden representarse, por ejemplo, por la probabilidad de que una computadora realice una tarea específica.

  Los diferentes tipos de Omega que representan la aleatoriedad de ciertos fenómenos computacionales parecen ser sólo los primeros derroteros en el gran mapa del azar que se ha comenzado a desplegar en las matemáticas. Becher ahora se aventura en un nuevo periplo, la conjetura de Grigorieff, que se refiere a la probabilidad de que un programa posea una propiedad que permita obtener un determinado resultado.

  Esta conjetura podría plantearse de la siguiente manera: si hubiera una inmensa bolsa que contenga todos los programas de computación posibles, la probabilidad de que uno de esos programas realice una acción tan específica como, por ejemplo, mostrar en el monitor de la computadora la consigna "luche y vuelve" es aleatoria: puede suceder o no.

  Omega es tan sólo un caso particular de un número aleatorio que responde a la conjetura, que aún no ha sido publicada, de Serge Grigorieff -profesor del Laboratoire d'Informatique Algorithmique, de la Universidad de París VII, Francia-, con quien investiga actualmente Becher.

La clasificación mágica

  Hasta hace muy poco tiempo, las elucubraciones matemáticas en torno al azar se mantuvieron en el terreno de la teoría pura. Pero, en la actualidad, están comenzando a vislumbrarse aplicaciones computacionales para estos trabajos teóricos.

  En este momento, Becher trabaja, junto con Santiago Figueira y los tesistas Martín Urtasun y Alejo Capparelli, sobre un algoritmo que inventó Paul Vitanyi, del Instituto Nacional de Investigaciones de Holanda (en la ciudad de Amsterdam), que sirve para clasificar archivos de una manera muy particular.

  "La idea de este algoritmo tiene que ver con una aproximación a la noción de complejidad descriptiva, es un algoritmo mágico -sorprende la investigadora-. Se ingresa un conjunto de archivos y el algoritmo los clasifica en clusters (grupos), sin un criterio especificado". Una de las pruebas realizadas con este algoritmo fue copiar todos los archivos de la computadora de Becher sin respetar los directorios en los que estaban ordenados, para que el algoritmo los reagrupara. El experimento dio como resultado un orden similar al original. "Yo tenía una estructura de directorios temática y ocurrió que el algoritmo consiguió reconstruir esa estructura. Los resultados experimentales que hay sobre archivos de texto son increíbles -se entusiasma-. Mejoramos el algoritmo de clusterización y analizamos qué cosas de la teoría de la complejidad algorítmica de Chaitin está usando".

  La clasificación que realiza este algoritmo no se basa en un discernimiento temático o semántico: no analiza contenido ni descripciones de los archivos (como los nombres o la extensión). El algoritmo permite realizar una clasificación de información con un criterio no especificado. La idea con la que trabaja es la siguiente: toma dos archivos (A y B), los junta y los compacta con algún programa (tipo Gzip o PkZip). Entonces, cuando se compara la longitud del archivo A compactado con la longitud de A-B compactado, si ambas longitudes son muy parecidas (si A-B no difiere de A), esto quiere decir que la información que contiene B ya está contemplada en A. Por lo tanto, A y B estarán en el mismo cluster.

  Como los algoritmos de compactación funcionan detectando patrones repetidos, desde la perspectiva de Chaitin, la longitud de un archivo compactado es una aproximación burda a la complejidad del mismo. "Si se utiliza Gzip, por ejemplo, nada garantiza que el resultado sea la descripción más corta del archivo -destaca la investigadora-. Otro programa de com-pactación podría haber hecho un mejor trabajo, por eso es una aproximación a la noción teórica de complejidad de largo de programa o complejidad descriptiva".

  Por el momento, ni Becher ni Chaitin tienen idea de para qué pueden servir concretamente los Omega e Hiperomega. Pero es de suponer que esas cifras elusivas puedan tener muchas aplicaciones. Sobre todo si se tiene en cuenta que hace millones de años un inmenso caldo de bacterias comenzaba a cocinarse al calor del sol, y que gracias a un condimento peculiar esa sopa transformó a la Tierra en este planeta pletórico de vida. Sí, casualmente, todo lo que existe es producto del azar.


El Padre de Omega

  Gregory Chaitin es un matemático bastante particular: se formó de manera autodidacta. No realizó ninguna carrera universitaria, aunque tomó algunos cursos en diversas universidades de Estados Unidos.

  Si bien nació en EE.UU., debido a que sus padres son porteños, pasó buena parte de su juventud en el barrio de Villa Crespo, donde vivió entre los 18 -edad en que publicó su primer paper científico en la revista de la Associaton for Computing Machinery- y los 28 años, época durante la cual siguió algunos cursos y enseñó en la FCEyN, donde todavía sigue dando clases periódicamente.

  Las investigaciones de Chaitin significaron importantes aportes en una zona donde se cruzan la matemática, la lógica y la teoría de la computación. Todo comenzó cuando en el año 1957 el joven Chaitin tomó unas clases de física en la Universidad de Columbia. En aquel momento, fascinado con la física cuántica y la teoría de la relatividad, descubrió que para entender esas cuestiones tenía que estudiar matemática. A eso se dedicó y, al poco tiempo, el inquieto adolescente se encontró con el teorema de la incompletitud de Gödel. Según Chaitin, esta proposición relativizaba muchas de las certezas matemáticas que se tenían hasta el momento.

  A partir de sus investigaciones pudo formular la Teoría Algorítmica de la Información, con la que propone medir la complejidad descriptiva de la información y establecer la cantidad mínima de palabras que se necesitan para expresar una definición. En la actualidad, este singular investigador trabaja en el IBM Watson Research Center en el estado de Nueva York.

(*) Centro de Divulgación Científica - FCEyN.

 

NOTICIAS | BREVIARIOS | CABLE SEMANAL | EDUCYT | EXACTAMENTE | LISTA EXACTAS
MICROSEMANARIO | OPINION | AGENDA | LIBROS Y REVISTAS | DOCUMENTOS