algorithm - complexity - o 1

¿Se puede encontrar una cadena de bits finita en pi dentro de un tiempo razonable?

Question

Entonces, hace un tiempo leí una broma que decía algo así:

"Nunca calcule pi en binario, porque es infinito y aleatorio, en teoría contiene todas las cadenas de bits finitas. Entonces, tendrá todo el material con derechos de autor en existencia y será responsable de algunas multas graves".

Obviamente, esto debe ser humorístico, pero me hizo pensar. Si cada cadena de bits finita existe en una representación binaria de pi, ¿sería posible usar esto como un método de transmisión de datos?

Por ejemplo, digamos que quería transmitir una cadena de bits que podría interpretarse como una imagen jpeg. En lugar de enviar la información directamente, encontraría su ubicación dentro de los dígitos de pi, y simplemente enviaría la ubicación del primer bit dentro de los dígitos de pi, así como las longitudes de la cadena.

Esto me parece bastante sencillo, pero la dificultad obvia aquí es que la probabilidad de encontrar esta cadena incluso dentro de los primeros trillones de dígitos es notablemente pequeña. Por lo tanto, podría terminar tomando una inmensa cantidad de tiempo para encontrar.

Mi pensamiento es que varias máquinas podrían dedicarse a buscar archivos grandes dentro de pi, y luego crear un índice de todas sus ubicaciones de inicio. Por lo tanto, cada cálculo solo tendría que ocurrir una vez y luego esa información podría transmitirse extremadamente rápido a partir de ese momento.

¿Entonces, qué piensas? ¿Es esto posible, o estos cálculos tomarían demasiado tiempo?

¡Gracias por leer! Pido disculpas si he pasado por alto cualquier guía de publicación, esto si es mi primera pregunta en este foro.

EDITAR:

Gracias por sus rápidas respuestas, amigos! Pensé que había un error en mi razonamiento, ¡es bueno saber por qué!

Answer 1

porque continúa infinitamente y es aleatorio, teóricamente contiene todas las cadenas de bits finitas

Pi continúa infinitamente, pero definitivamente no es aleatorio, es decir. sus dígitos se pueden calcular mediante un programa de tamaño O(log n) (y, por lo tanto, los prefijos finitos pueden generarse con programas mucho más pequeños que los prefijos), lo que significa que la complejidad de Kolmogorov de los prefijos de Pi es asintóticamente menor que su tamaño. Por lo tanto, aún no se ha probado que contenga cada cadena finita (no lo sé).

Answer 2

Ampliando mis comentarios. Hay un concepto muy importante aquí que se llama entropía de información .

Fuera de la divulgación completa, soy el actual récord mundial de los dígitos de Pi en 10 billones de dígitos (10 ^ 13).

Tengo aproximadamente 10,000 copias del número de seguridad social de todos.

Sin embargo, eso no significa que pueda hackear las cuentas de todos y robar sus identidades. Porque no sé dónde empieza el SSN de cada persona. Y para un SSN típico de 9 dígitos, el primer dígito en Pi donde aparecerá ese SSN será del orden de 9 dígitos. En otras palabras, la información sobre el SSN se guarda en la dirección en lugar de en la propia Pi.

Por ejemplo, si alguien tiene el SSN: 938-93-3556

Comienza en offset 597,507,393 en Pi. Ese número 597,507,393 es aproximadamente tan largo como el SSN en sí. En otras palabras, no hemos ganado nada usando Pi.
_{(No estoy seguro de si hay un desplazamiento anterior donde aparece, pero la probabilidad disminuye exponencialmente con compensaciones más pequeñas).}

Para generalizar esto, incluso si tiene infinitos dígitos de Pi (que en teoría contiene toda la información posible), la dirección que contiene los datos XXX (con extrema probabilidad) será tan grande como la propia XXX.

En otras palabras, la información no se mantiene en los dígitos de Pi, sino en la dirección donde comienza la información.

Answer 3

Como estábamos todos aburridos en el Lounge seguí adelante e implementé una búsqueda para averiguar las compensaciones promedio de los ''mensajes'' de longitudes específicas.

Descargué 1 millón de dígitos de Pi y busqué todas las subsecuencias de longitud fija (por ejemplo, 00..99). Dependiendo de la longitud del mensaje, obtendrás los siguientes resultados:

 Digits    Avg.Offset    Unfound

 1            8.1        0
 2          107.07       0
 3          989.874      0
 4         9940.46       0
 5        99959.4        8 <-- note

Tenga en cuenta que al 10% de la cantidad de dígitos de pi buscados , ya comenzamos a encontrar patrones no encontrados.

También tenga en cuenta que, según lo predicho por las leyes de la entropía de la información, el desplazamiento promedio es aproximadamente proporcional a la longitud del mensaje.

Salida cruda y tiempos:

Corriendo

for a in 10 100 1000 10000 100000; do /make -B CFLAGS=-DNUMRANGE=$a && time ./test; done

Espectáculos

g++ -DNUMRANGE=10 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
81 cumulative, 8.1 average

real    0m0.008s
user    0m0.008s
sys 0m0.004s
g++ -DNUMRANGE=100 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
10707 cumulative, 107.07 average

real    0m0.004s

g++ -DNUMRANGE=1000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
989874 cumulative, 989.874 average

real    0m0.010s

g++ -DNUMRANGE=10000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
9.94046e+07 cumulative, 9940.46 average

real    0m0.081s

g++ -DNUMRANGE=100000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
8 unfound
9.99594e+09 cumulative, 99959.4 average

real    0m7.387s

Código completo, makefile y dígitos pi: https://gist.github.com/3062541

Answer 4

Esa afirmación es incorrecta. Pi es infinito, y su siguiente dígito es impredecible, pero eso no significa que todas las cadenas posibles estén ahí.

Por ejemplo, supongamos que creo una función similar a pi, pero cada vez que hay una secuencia de 20 ceros binarios, calculo los siguientes 20 bits, y reemplace los ceros con ella.

Esa secuencia también es infinita e impredecible, pero podemos saber con certeza que nunca contiene una secuencia de 20 ceros binarios.

No hay forma de probar que PI contiene cada secuencia posible de bits.

Esto también podría ayudar a responderla: http://www.youtube.com/watch?v=8PUJvAlD64k

Answer 5

No, no es posible encontrar de manera eficiente una secuencia arbitraria en una secuencia aleatoria, que sigue a la definición de "aleatorio". (Si hubiera una manera de predecir dónde se produjo la secuencia, no sería aleatoria).

En cuanto a la indexación de todas las ubicaciones, bueno, ¿qué has ganado? Básicamente, estás diciendo "Saltar al punto de inicio 0 ..." y luego debes decir "... y luego calcular los siguientes bits de tamaño JPEG en π ..." (no se gana, ya que tienes que usar aumente la energía haciendo el cálculo) o "... y luego busque la siguiente porción de datos de tamaño JPEG en el índice mega-π". (En cuyo caso podría, simplemente, cargar el archivo JPEG).

No puedes ganar y no puedes llegar a un punto de equilibrio (y, por lo que vale, no puedes salir del juego).

ACTUALIZACIÓN: @ La respuesta de Mysticial es mejor que la mía. Su punto

Por ejemplo, si alguien tiene el SSN: 938-93-3556

Comienza en offset 597,507,393 en Pi. Ese número 597.507.393 es aproximadamente tan largo como el SSN en sí. En otras palabras, no hemos ganado nada usando Pi.

Captura elegantemente el problema fundamental.