Может ли какая-либо конечная битовая строка быть найдена в pi в течение разумного промежутка времени?

Итак, некоторое время назад я прочитал анекдот, который пошел примерно так:

"Никогда не вычисляйте pi в двоичном виде, потому что он продолжается бесконечно и является случайным, он теоретически содержит каждую конечную битовую строку. Таким образом, вы будете иметь все материалы, защищенные авторским правом, и нести ответственность за некоторые серьезные штрафы".

Это, очевидно, должно быть юмористическим, но это заставило меня задуматься. Если каждая битовая строка существует в двоичном представлении pi, можно ли использовать это как способ передачи данных?

Например, скажем, я хотел передать битовую строку, которая может быть интерпретирована как jpeg-изображение. Вместо того, чтобы напрямую отправлять информацию, я бы нашел ее местоположение в цифрах pi и просто отправил местоположение первого бита в цифрах pi, а также длины строки.

Для меня это кажется довольно простым, но очевидным препятствием здесь является то, что вероятность нахождения этой строки в пределах даже первых нескольких триллионов цифр чрезвычайно мала. Таким образом, это может в конечном итоге взять огромное количество времени, чтобы найти.

Мое мышление состоит в том, что несколько машин могут быть предназначены для поиска больших файлов внутри pi, а затем создания индекса всех начальных местоположений. Таким образом, каждое вычисление должно происходить только один раз, а затем эта информация может быть передана очень быстро с тех пор.

Итак, что вы думаете? Возможно ли это, или эти вычисления занимают слишком много времени?

Спасибо за чтение! Прошу прощения, если я упустил какие-либо рекомендации по проводке, это, если мой первый вопрос на этом форуме.

EDIT:

Спасибо за ваши быстрые ответы, ребята! Я подумал, что в моих рассуждениях была ошибка, приятно знать, почему!

Ответ 1

Расширение моих комментариев. Здесь очень важная концепция, которая называется информационной энтропией.

Из полного раскрытия я являюсь держателем мировой рекордной цифры Pi на 10 триллионов цифр (10 ^ 13).

У меня есть примерно 10 000 экземпляров всех номер социального страхования.

Однако это не значит, что я могу просто взломать все аккаунты и украсть их личности. Потому что я не знаю , где запускается SSN каждого человека. И для типичного 9-значного SSN первая цифра в Pi, где будет отображаться SSN, будет иметь порядок 9 цифр. Другими словами, информация о SSN хранится в адресе, а не в самом Pi.

Например, если у кого-то есть SSN: 938-93-3556

Он начинается со смещения 597 507 393 в Pi. Это число 597,507,393 примерно такое же, как и SSN. Другими словами, мы ничего не получили, используя Pi.
_{(Я не уверен, есть ли более раннее смещение там, где оно появляется, но вероятность экспоненциально уменьшается с меньшими смещениями.)}

Чтобы обобщить это, даже если у вас были бесконечные цифры Pi (который теоретически содержит всю возможную информацию), адрес, который хранит данные XXX, будет (с крайней вероятностью) размером до самого XXX.

Другими словами, информация не хранится в цифрах самого Pi, а скорее адрес, на котором начинается информация.

Ответ 2

Поскольку нам все было скучно в Lounge, я пошел дальше и реализовал поиск, чтобы узнать средние смещения "сообщений" определенной длины.

Я загрузил 1 миллион цифр Pi и искал все подпоследовательности фиксированной длины (например, 00..99). В зависимости от длины сообщения вы получаете следующие выходы:

 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

Обратите внимание, что при 10% числа разрядов pi, мы уже начинаем наносить необоснованные шаблоны.

Заметим также, что, как предсказывает законы информационной энтропии, среднее смещение примерно пропорционально длине сообщения.

Сырой выход и тайминги:

Запуск

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

Отображение

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

Полный код, makefile и цифры pi: https://gist.github.com/3062541

Ответ 3

Нет, невозможно эффективно найти произвольную последовательность в случайной последовательности - это следует из определения "случайный". (Если бы был способ предсказать, где произошла последовательность, это не было бы случайным.)

Что касается индексации всех местоположений, ну, что вы получили? Вы, по сути, говорите "Перейти к начальной точке 0...", а затем вам нужно сказать "... и затем рассчитать следующие бит размера JPEG в & pi;..." (нет победы, поскольку вам нужно используйте энергию, выполняющую расчет) или "... и затем просматривайте следующий размер данных JPEG размером в мега-индекс". (В этом случае вы могли бы просто загрузить файл JPEG.)

Вы не можете победить, и вы не можете сломаться (и, для чего это стоит, вы не можете выйти из игры).

UPDATE: @Мистический ответ лучше, чем мой. Его точка

Например, если у кого-то есть SSN: 938-93-3556

Он начинается со смещения 597 507 393 в Pi. Это число 597 507 393 составляет примерно столько же, сколько и SSN. Другими словами, мы ничего не получили, используя Pi.

изящно фиксирует фундаментальную проблему.

Ответ 4

Это утверждение неверно. Pi бесконечен, и его следующая цифра непредсказуема, но это не означает, что там есть всякая возможная строка.

Например, предположим, что я создаю функцию, похожую на pi, но в любое время есть последовательность из 20 двоичных нулей, вычисляет следующие 20 бит и заменяет нули на нее.

Эта последовательность также бесконечна и непредсказуема, но мы можем с уверенностью знать, что она никогда не содержит последовательность из 20 двоичных нулей.

Невозможно доказать, что PI содержит все возможные последовательности бит.

Это также может помочь ответить на него: http://www.youtube.com/watch?v=8PUJvAlD64k

Ответ 5

поскольку он продолжается бесконечно и является случайным, он теоретически содержит каждую конечную разрядную строку

Pi продолжается бесконечно, но определенно не является случайным - т.е. его цифры могут быть вычислены программой размера O(log n) (и, следовательно, конечные префиксы могут быть сгенерированы программами, намного меньшими префиксов), что означает, что сложность Префикса Pi в Колмогорове Pi асимптотически меньше их размера. Поэтому еще не доказано, что он содержит каждую конечную строку (я этого не знаю).