En búsqueda del azar

Para abordar los fundamentos esenciales de los modelos de cómputo, investigadores del Instituto de Ciencias de la Computación (ICC) trabajan en diferentes problemas vinculados al azar y los autómatas.

Desde sus inicios la Teoría de la Computación considera distintos modelos de cómputo. De este modo se consolidaron 3 modelos principales: los autómatas finitos (que son las máquinas de computar más sencillas), las máquinas de Turing (las computadoras usuales de hoy en día) y las computadoras cuánticas (cuyo funcionamiento no es digital). Cada modelo de cómputo determina qué problemas se pueden solucionar usando este tipo de dispositivo y qué problemas no. También determina a qué velocidad máxima y mínima pueden resolverse los problemas.  Y, más sorprendente aún, cada modelo de cómputo determina una noción de aleatoriedad, o dicho de otro modo: “azar”.

Para abordar estos temas que hacen a los fundamentos de la disciplina, investigadores del Instituto de Ciencias de la Computación (ICC) trabajan en diferentes problemas vinculados al azar y los autómatas.

Pero antes de adentrarnos en este asunto, ¿qué se entiende por “azar”? Si se piensa el azar en secuencias de símbolos, como 0 y 1, o letras del abecedario (a, b, c) o de cualquier alfabeto; una de esas secuencias resulta azarosa cuando no se la puede nombrar de forma más abreviada que la secuencia misma. “La única manera de nombrar una secuencia azarosa es, esencialmente, explícitamente. Sino, las secuencias azarosas tendrían una forma abreviada y una ley de formación de la secuencia, responderían a un patrón”, explica Verónica Becher, investigadora del ICC, doctora en ciencias de la computación y profesora del DC.

Ahora bien, ¿cuánto se conoce hasta el momento sobre el azar?  Para responder esa pregunta debemos remontarnos al año 1909 cuando Émile Borel, matemático francés, fue quien primero propuso una definición elemental de azar para secuencias infinitas. Esta definición de azar elemental se denomina “Normalidad”.  Borel se dio cuenta de que en una secuencia azarosa todos los símbolos deben tener las mismas chances de aparecer, sino la secuencia se volvería un tanto predecible. Por ejemplo, si consideramos los símbolos 0 y 1, el 0 debe aparecer la mitad de las veces y el 1 también. Y por la misma razón, todo par de símbolos deben tener la misma chance de aparecer, por lo que el 00, 01, 10, 11; cada uno debe aparecer un cuarto de las veces. Y así siguiendo para bloques de tres símbolos, cuatro símbolos, etc.

En 1933 David Champernowne, un estudiante de matemática en Cambridge y  compañero de Alan Turing, demostró que la secuencia 123456789101112131415161718192021222324252627282930…que se consigue concatenando todos los números enteros positivos en orden natural es una secuencia Normal.   Sí, es Normal, pero ¿es azarosa? A nosotros nos resulta completamente predecible. Tan predecible, que se puede hacer un pequeñísimo programa que compute esta secuencia infinita, arrojando un símbolo tras otro. “Este es el nivel de azar más bajo que casi no amerita llamarse ‘azar’ para nosotros, que conocemos el orden natural. Tampoco amerita llamarse ‘azar’ para las computadoras modernas (máquinas de Turing).  Sin embargo, para un autómata finito la secuencia de Champernowne es impredecible porque el autómata finito no puede darse cuenta cuál es la ley de formación. Podemos programar un autómata finito para que lea una secuencia,  un símbolo tras otro, y se comporte de manera diferente si el 0 y el 1 no aparecen con la misma frecuencia, o si algún bloque aparece más frecuentemente que otro. Pero ningún autómata finito puede considerar operaciones aritméticas como la  ley de formación de ‘sumar 1’ que tiene la secuencia de Champernowne”, afirma Becher.

Como se explicó anteriormente, las máquinas de Turing son más poderosas que los autómatas finitos y por lo tanto pueden predecir muchas secuencias que los autómatas finitos no pueden. Sin embargo,  las máquinas de Turing no pueden predecirlo todo. Hay un sinnúmero de secuencias que son azarosas para las máquinas de Turing. ¿Y esas secuencias pueden ser predichas por alguna otra máquina? El mismo  Alan Turing, padre de la computación moderna, concibió un modelo de cómputo más poderoso, que es el cómputo con “oráculos”. “Este modelo de cómputo considera cómo actuaría una máquina si tuviera infinita información adicional. El modelo abstracto de cómputo con oráculos en la actualidad se corresponde con un fenómeno corriente, que es el cómputo interactivo con el usuario, donde los datos que brinda el usuario son tomados por un programa y guían el cómputo. El usuario es el propio oráculo”, puntualiza Becher. Y acentúa, “una máquina de Turing con oráculo puede ser más poderosa que una sin oráculo, por lo que algunas de las secuencias que eran azarosas para una máquina de Turing, se pueden volver predecibles”.

Las máquinas de Turing son más poderosas que los autómatas finitos y por lo tanto pueden predecir muchas secuencias que los autómatas finitos no pueden. Sin embargo,  las máquinas de Turing no pueden predecirlo todo. Hay un sinnúmero de secuencias que son azarosas para las máquinas de Turing.

La investigadora del ICC está liderando un proyecto de investigación en Aleatoriedad y Máquinas de Estado Finito (autómatas). Uno de sus desafíos más importantes consiste en realizar programas para máquinas de Turing que generen secuencias azarosas para autómatas finitos (es decir, que generen secuencias  normales en el sentido de Borel) pero altamente impredecibles: “Se necesita inventar un generador pseudoaleatorio  que arroje secuencias infinitas sin período. Los actuales generadores pseudoaleatorios tiene período”, detalla  Becher.

Con la tecnología actual, al activar un generador pseudoaleatorio (valga el ejemplo de las máquinas electrónicas de los casinos) se lo asocia a un período, tan largo como uno quiera. Pasado el período, la secuencia se repetirá exactamemente igual. Es por ello que las aplicaciones de hoy en día utilizan generadores pseudoaleatorios y se comprometen a tener un período máximo. “Esto entra en conflicto con la era de Internet, donde todos los programas están pensados para no detenerse, es decir, para no tener un momento de reseteo, porque la comunicación es un continuo. Vale aclarar que lo que  llamo ‘la era de Internet’ es exactamente la concepción de cómputo infinito propuesta por Turing. Y es con la que hoy se concibe el mundo en que vivimos, con cómputo interactivo en tiempo real, con la idea de seguir para siempre”, sostiene la investigadora.

En este contexto, si el cómputo es infinito en tiempo, entonces  los generadores pseudoaleatorios sin período resultan una necesidad práctica y no solamente un problema teórico.  “El problema ya está instalado y ahora se buscan soluciones posibles. Este desafío viene con una meta adicional, esencial para las aplicaciones modernas, y es que los generadores pseudoaleatorios deben computar muy  rápido”, concluye Becher.