Las computadoras no juegan a los dados (El problema de crear una función aleatoria)

Jorge Luis Borges, en su cuento "La lotería en Babilonia", nos presenta la vida del pueblo de Babilonia que fue entregando progresivamente su destino a manos de "la corporación". Este misterioso poder, que nació como una simple empresa de lotería, dicta desde las sombras los destinos de cada habitante de esta ciudad. La participación en los sorteos es obligatoria y los resultados  establecen la fortuna hasta el próximo sorteo. El "premio" puede ser dinero, pero las opciones son mucho más amplias, incluso pueden ser castigos. Desde ser elegido proconsul, ser encarcelado, abrir una ánfora y encontrar una víbora o encontrarse con la mujer amada. Los sorteos son secretos y de gran complejidad. Por lo tanto sus resultados toman por sorpresa a sus destinatarios.

Libro "Ficciones" donde
se encuentra el cuento "
La lotería de Babilonia"

La compañía es omnipresente y muchos dudan incluso de su existencia. Su accionar es invisible e inseparable de los azarosos avatares de la vida. Un conjunto de ciudadanos sugieren que había dejado de existir hace tiempo. Otros que solo define pequeñas cosas, como el grito de un pájaro. En última instancia su misma presencia para los hombres ya resultaba irrelevante.

En el cuento de Borges, el azar producto de una construcción humana se mezclaba hasta ser inseparable con el producido por la naturaleza. Y este logro para quienes trabajamos con computadoras intentando realizar procesos aleatorios es más difícil de lo que uno se imagina.

Desde la construcción de la primera computadora y a medida que más procesos se iban informatizando, la necesidad de una función aleatoria se hacía evidente. Dentro del mundo de los juegos, en la simulación científica, o en la seguridad informática poder contar con un valor que a priori no se pueda adivinar es indispensable. Podemos encontrar diversas formas de generar valores al azar en nuestra vida diaria, como lanzar una moneda o un dado. Sin embargo, realizar un proceso similar utilizando la computadora no es sencillo. ¿Cúal es el problema?

Una computadora - sin importar lo moderna que sea - es en rigor una máquina de Turing. Un artilugio que tiene un set de instrucciones y puede ejecutar un programa (un conjunto ordenado de esas instrucciones) para resolver un problema especifico. El mismo Alan Turing se interesó en determinar que tipo de programas o algoritmos podía ejecutar en un tiempo finito su invención. Pudo determinar que ciertos problemas no podían resolverse y a estos se los conoce como "no computables".

¿Es una función aleatoria no computable?. La definición de complejidad de Kolmogórov puede responder a esta pregunta. Este enunciado afirma que la cantidad de información de una fuente (un emisor de mensajes) está definida por la longitud del mínimo programa para reproducirlo. 

Por ejemplo si tengo un listado del tipo "A,A,A,A,A,A..." (podrían ser 10, 100, 1 millón o infinitos). Un programa sencillo que lo reconstruya podría ser:

repetir (       imprimir "A"    )

De forma similar, agregando un poco de complejidad, si tengo un listado del tipo "1,2,3,4,5...", el programa para reproducirlo sería:

n=1 repetir (       imprimir n    n=n+1 )

Andréi Nikoláyevich
Kolmogórov

Este mismo algoritmo cambiando el número inicial o el valor a incrementar emitiría otro listado diferente, pero de igual complejidad. Podemos construir algoritmos para generar distintos decimales del número pi (por ejemplo con el algoritmo de Gauss-Legendre). También podemos codificar un programa para emitir la sucesión de Fibonacci. Otros algoritmos, más complejos  incluyen a los métodos de compresion de archivos sin perdida de información (LZw, PPMC, etc).

Cuando mayor complejidad, mayor será el tamaño del algoritmo para reproducirlo y más complejo el set de datos iniciales para alimentarlo. En el caso extremo el tamaño del algoritmo y set de datos más pequeño para reproducir una serie es de igual o mayor tamaño que la serie misma. Y si el algoritmo generador es más grande que la salida emitida, por qué no emitir directamente el archivo original?

Una fuente aleatoria, por ejemplo un dado, es impredecible. Podemos ejecutar 10 tiradas de dados y anotar sus resultados y aventurarnos (y seguramente con algo de trabajo podemos lograrlo) a construir un programa que emita el resultado anterior. Podemos repetir el mismo trabajo con 100 tiradas y con 1000. Cada vez nos costará más hallar un algoritmo. Si el dado no está trucado, cualquier cara tendrá la misma probabilidad de aparecer y las combinaciones de sus apariciones no harán más que hacernos más difícil hallar un patrón (aunque sea ficticio). En el límite, un imaginario lanzamiento de infinitos dados, encontrar un algoritmo será imposible. No porque sea complicado encontrar un patrón, sino por su inexistencia. Cualquier algoritmo que podría crearse para resolverlo, sería mas grande que registrar la infinita sucesión de lanzamientos.

La imposibilidad de crear una función aleatoria en una computadora fue apreciado desde los inicios mismos de su invención. De igual forma se notó su utilidad extrema. Por lo tanto diferentes propuestas fueron siendo probadas. En la construcción de la computadora Manchester Mark I, el mismo Alan Turing propuso crear un mecanismo externo para generar la función. Esta computadora, la primera en permitir almacenar el programa a ejecutar al igual que sus datos vio la luz en 1948. Lamentablemente no lograron hacer confiable dicha funcion. Al respecto Martin Campbell-Kelly en su publicación “Programming the Mark I: Early Programming Activity at the University of Manchester” detalla:

"At the request of Turing an instruction to generate a random number from a noise source was provided. Unfortunately, the numbers turned out to be not particularly random, and debugging was difficult because programmes were not repeatable; consequently the instruction fell into disuse."

Un hito importante fue la creación del libro "A Million Random Digits with 100,000 Normal Deviates" creado por la corporación RAND y publicado en 1955. Esta publicación cumplía con lo que su titulo indicaba. Se compilaban 1 millón de dígitos (entre 0 y 9) recopilados mediante una computadora IBM conectada a una ruleta electrónica. La compilación de esos dígitos comenzó en 1947 y luego de varias pruebas para comprobar su robustez se terminaron publicando. El artículo, de 1949, "History of RAND's random digits - Summary" relata como era su funcionamiento y los test realizados. El libro fue fuente de consulta y material de pruebas para gran cantidad de personas.

Para 1957 la lotería de Reino Unido "Premium Bond" comenzó a utilizar un proceso de sorteo automatizado. Para eso contaron con ERNIE (Electronic Random Number Indicator Equipment) que mediante tubos de neón generaba los números aleatorios. Las variaciones eléctricas permitían generar de forma aleatoria los números ganadores. Seguramente para evitar desconfianzas generaron un video explicando su funcionamiento y su efectividad.

La primera ERNIE fue utilizada hasta 1972, su arquitectura estuvo basada en la computadora Colossus. Ahora, retirada, descansa en el museo de la ciencia de Londres desde 2008.

Desde el Fourmilab en Suiza  surgió en 1986 otro método de calcular valores random. Para eso se utiliza un contador Geiger-Müller que mide el decaimiento radioactivo de un núcleo de Cesio-137.  HotBits, tal como es su nombre, explica su funcionamiento en su sitio web, provee una interface para solicitar números aleatorios y una librería java para integrarlo en un programa.

Lámpara de lava

Otro ejemplo de una propuesta fue la desarrollada por SGI (Silicon Graphics). Entre 1997 y 2001 un sitio de internet de la empresa mostraba su funcionamiento. Para generar un valor aleatorio se utilizaban un conjunto de lámparas de lava que por su naturaleza caótica presentaba continuamente diferentes formas. Al capturar una fotografía de un instante de aquellas se realizaba una digitalización y de ahí un proceso para tomar el valor aleatorio. El proyecto no existe más, pero ya al ser en la era de internet podemos rastrear algo en web.archive.


También en 1997 se creó la semilla del servicio de generación de números aleatorios RANDOM.ORG. Inicialmente fue un proyecto de una "start up" de 4 amigos para crear una máquina para apuestas. Luego, al truncarse esa iniciativa, unos de sus creadores continuó refinando el prototipo en su paso por sus estudios universitarios. Utilizando como fuente de generación una simple radio, capta los ruidos atmosféricos para generar una señal de ruido blanco. Actualmente provee servicios de generación de números aleatorios utilizando el mismo principio.

Tanto Intel como AMD agregaron - 1999 y 2015 respectivamente - una instrucción dentro de sus set de sus procesadores que obtiene un valor aleatorio en base a las fluctuaciones térmicas de un resistor. También hay proyectos caseros para crear propios generadores de números aleatorios.

Cualquier fuente no determinística de la naturaleza se podría poner como entrada a una computadora para tener una función aleatoria. Se debe prestar especial atención a la calidad de la fuente, puesto que una mala implementación o la elección de una fuente que no sea realmente aleatoria tiraría por la borda toda construcción realizada sobre esta premisa. Por ese motivo es necesario realizar test de validación. Se debe observar que los resultados estén uniformemente repartidos y que sean estadísticamente independientes entre si.

Todo lenguaje de programación tiene un conjunto de métodos para generar valores aleatorios. ¿Eso implica que toda computadora viene con un generador de números aleatorios integrado? No. La realidad es que en la mayoría de los casos la computadora nos estará dando un número no aleatorio. Pero que a afectos prácticos en la mayoría de los casos servirá a su propósito. ¿Qué es lo que obtenemos? Un número generado por una función pseodo-aleatoria. Como funciona esta es material para un próximo artículo.