KAPOW!

En el grupo de investigación que dirige Verónica Becher se utilizan modelos computacionales para dar ejemplos de secuencias normales, es decir secuencias en las que ningún bloque de símbolos aparezca con mayor frecuencia que los demás bloques de la misma longitud. Aunque el tema parezca extremadamente abstracto se ha podido utilizar, por ejemplo, para resolver problemas sobre secuencias naturales, como genomas o proteínas.

“Me niego a creer que Dios juega a los dados con el universo”, dijo Albert Einstein, o más bien escribió en una carta a su colega, el físico Max Born. Y, aunque algunos han querido interpretar la frase como una defensa del determinismo religioso, el contexto en el que fue escrita indica que se trataba de una crítica a la mecánica cuántica y el principio de incertidumbre de Heisenberg, un concepto de aleatoriedad que al genial físico le costaba aceptar. Sin embargo, en esta, Einstein se equivocó: es posible que -de existir- Dios sí juegue de a rato a los dados, al menos en lo que a la mecánica cuántica se refiere. Por otra parte, para la ciencia de la computación actual, tal vez la “aleatoriedad” de un juego de dados no sea tan impredecible como Einstein temía.

“Todos tenemos una idea intuitiva de qué es el azar, típicamente asociada con el juego o con la suerte. Decimos que la suerte es loca, porque es imposible predecirla, no tiene leyes de formación, no tiene patrones. Pero sabemos que caras y cecas deben salir, a la larga, la misma cantidad de veces; y que si mezclamos bien las cartas y jugamos el suficiente tiempo, alguna vez me tocará el as de espadas, el as de basto y el 7 de espadas; más aún, a la larga, esta combinación saldrá tanto como cualquier otra combinación de tres cartas. Esta es la condición más básica del azar y se llama normalidad”, explica Verónica Becher, directora del grupo de investigación en problemas y algoritmos sobre secuencias, Kapow.

Una secuencia infinita de símbolos -por ejemplo ceros y unos- es normal si ningún bloque de símbolos aparece con mayor frecuencia  que los demás bloques de la misma longitud.

Esta definición fue dada por Émile Borel hace más de cien años y, desde entonces, la mayoría de las preguntas han quedado abiertas. Entre ellas, si constantes matemáticas como “Pi” que son números que tienen infinitas cifras decimales no periódicas, tienen expansiones decimales normales. Es decir, si en la cola infinita de dígitos que vienen después de la coma, ninguno aparece con mayor frecuencia que los demás y tampoco ningún bloque de dígitos aparece con mayor frecuencia que los demás bloques de la misma longitud. Se cree que sí.

“La noción de azar exige, por encima de la condición básica de normalidad, la de impredecibilidad. Para que una secuencia sea azarosa tiene que ser imposible poder predecir sus símbolos. En la jerga de los  jugadores, se diría que no hay martingala capaz de  ganar sobre secuencias aleatorias”, afirma Becher. Pero, ¿impredecible para qué habilidades? Aquí entran en escena las ciencias de la computación.

Hay muchos modelos de cómputo y difieren en su capacidad de resolver problemas, “del mismo modo que un destornillador resuelve problemas distintos que un martillo”, grafica Becher. El modelo de mínima capacidad es el  autómata finito, ya que tiene memoria finita y opera en tiempo lineal respecto del tamaño de la entrada. El modelo de cómputo de máxima capacidad es la máquina de Turing. La computadora que los investigadores tienen en  su escritorio es un ejemplar de este modelo.

“Nosotros nos dedicamos a dar ejemplos de secuencias normales que satisfacen restricciones, por ejemplo, que tengan autosimilaridad, alta velocidad de convergencia a normalidad, y, en ciertos casos, damos algoritmos para computarlas eficientemente. También nos interesa resolver problemas sobre secuencias naturales, como genomas o proteínas, y hemos trabajado sobre familias de secuencias repetitivas en colaboración con el Laboratorio de Fisiología de Proteínas del Departamento de Química Biológica. Actualmente nos preocupa cómo definir (y certificar) la independencia entre secuencias aleatorias y de qué manera, a partir de una secuencia aleatoria hecha de dos símbolos, podemos construir otra hecha de tres símbolos”, explica la directora de este grupo de nombre extraño. “El grupo KAPOW, tan inusual como su nombre, nació el 2009 con el desafío de hacer un algoritmo ultra rápido para comparación de genomas enteros (ADN), en base al cómputo exhaustivo de todas las repeticiones exactas (del largo que fueran). Y lo hicimos”, dice Becher a la vez que aclara que, si bien KAPOW es la sigla en inglés de Knowledgeable Algorithms for Problems On Words, también es la onomatopeya más usada en el comic de Batman. “Nos gustó como nombre para nuestro grupo, es un golpe seco, exacto, un knock out que liquida el problema”.

Desde hace más de cien años, los resultados en este área han sido mucho más fáciles de conjeturar que de demostrar, a pesar de que notables matemáticos –como Borel, Turing y muchos otros- han trabajado en estos problemas. “A pesar de estos esfuerzos seguimos sin saber casi nada acerca de las expansiones decimales de los números reales y las interrelaciones entre sus propiedades combinatorias, de teoría de números y  computacionales. Sin embargo, acuerdo con el semiólogo y matemático Charles Sanders Peirce cuando sostiene que los saberes científicos llegan, a la larga, a la verdad. Yo apuesto como él”, concluye Becher.