¿Existe una secuencia de bits perfectamente aleatoria?

Necesitamos determinar una forma de encontrar cuán aleatoria es cualquier secuencia de bits dada. Lo que puede ayudarnos aquí es el concepto de complejidad de Kolmogorov. En términos generales, KC es la longitud del algoritmo más corto que produce esa secuencia. La idea es que un algoritmo es una representación comprimida de una secuencia, y la compresión depende de cuánto patrón hay en la secuencia. Cuanto más corto es el algoritmo, mayor es la compresión, lo que indica un patrón fuerte y una falta de aleatoriedad. Una cadena se puede llamar aleatoria cuando el algoritmo más corto tiene la misma longitud que la cadena misma. Esto significa que la cadena no permite compresión y no tiene patrón.

¿Existen tales secuencias? ¡Oh sí! De hecho, casi todas las secuencias infinitas son aleatorias en este sentido.

Lo que es aleatorio no es el resultado, sino el proceso que produce el resultado.

Si lanzas un dado, obtendrás un resultado particular, por ejemplo, 4. El número 4 no es aleatorio. Lo que es aleatorio es el proceso que produce ese resultado, el lanzamiento del dado.

Del mismo modo, puede tener un proceso que produce una secuencia aleatoria de bits. Por ejemplo, lanzar repetidamente una moneda. El resultado que obtienes, algo así como THHTHTTTHTHHHHTHT, etc., es un resultado particular y, como el número 4 anterior, no es aleatorio. No es más o menos aleatorio que el resultado HHHH … de todos los H’s.

Entonces, sí, es posible tener un proceso que produzca una secuencia aleatoria de bits.

Si quiere decir si es posible generar electrónicamente bits puramente aleatorios, con el uso de un flip-flop activado por el borde puede acercarse.

En el circuito anterior, cuando T es alto, el flip flop alterna rápidamente a intervalos aleatorios y cuando T es bajo, la salida es constante. No importa si la fuente de ruido no es perfectamente blanca. Lo que importa es que no hay forma de saber cuántas veces el flip flop cambia mientras T es alto, de modo que cuando T baja, hay una probabilidad lo suficientemente cercana al 50% de que la salida sea alta o baja.

Si introduce la salida en un registro de desplazamiento, puede generar una palabra aleatoria.