Колмогоровская сложность и число Пи

[Lesobrod]

Недавно столкнулся с этой темой, прошу прощения за наивность вопроса.
Рассмотрим последовательность вида 10010110... и т.п. Степень её хаотичности/непредсказуемости характеризуется ( в частности) длиной программы, которая сможет выдавать такую последовательность. Ясно, что для даже бесконечной цепочки вида 101010101.. программа получится совсем небольшая, а вот совершенно хаотичный набор можно только предъявить как есть - его же длина и будет длиной программы.
Рассотрим цифры числа Пи. В настоящее время известно несколько эффективных алгоритмов их получения. Они, конечно, не совсем короткие, но явно конечной длины. Между тем встретил сообщение, что буквально недавно доказана хаотичность, полная независимость цифр Пи.
Как это можно увязать?

[AD]

Lesobrod в сообщении #299669 писал(а):

Между тем встретил сообщение, что буквально недавно доказана хаотичность, полная независимость цифр Пи.
Как это можно увязать?

Хотелось бы посмотреть на точную формулировку результата. Не могли бы Вы дать ссылку?

P.S. Ну а что такого? Ну программа выдаёт хаотичную последовательность цифр, не зависящих друг от друга, ну и что?

[gris]

Да, но только если запустить ей ещё раз, она выдаст точно такую же последовательность цифр. А хороший датчик случайных чисел каждый раз будет выдавать разное. Правда у меня сомнение - алгоритм, выдающий бесконечное число знаков пи, действительно конечен? И действительно ли конечность алгоритма связана со сложностью?

[Lesobrod]

Пока вот что: http://www.inauka.ru/news/01-09-02/article28705
Сейчас ищу более серьёзную ссылку на аглицком.
А противоречие вот в чем - программа конечной длины может выдавать только
псевдослучайные числа.Они могут удовлетворять одному из критериев хаотичности, но не всем.
Например, если они вычисляются по рекуррентному правилу$x[n+1]=F(x[n-1])$, то у них явно ненулевая взаимная корреляция, а значит, это не чистый хаос.
Между тем, и ранее предполагалось, а теперь как-бы доказано, что цифры Пи полностью хаотичны, в том числе взаимонезависимы.

[e7e5]

gris в сообщении #299680 писал(а):

А хороший датчик случайных чисел каждый раз будет выдавать разное.

Теоретически?
Практически такую "машинку" не сыскать видно...
Это ж если и есть такая машинка, то сколько ж проверять потребуется?..., какой-то замкнутый круг

[AD]

Lesobrod в сообщении #299681 писал(а):

А противоречие вот в чем - программа конечной длины может выдавать только псевдослучайные числа. Они могут удовлетворять одному из критериев хаотичности, но не всем.

Ну вот это муть какая-то до тех пор, пока Вы не определитесь, что такое "все критерии хаотичности", а также не объясните, что в том результате доказано соответствие именно всем критериям. Для этого точный результат и хочется почитать, а не журналистскую воду.

Там, видимо, про нормальность числа пи говорится, то есть про то, что все последовательности цифр данной длины в нём встречаются одинаково часто, да? Как бы ну и что, вон по ссылке "гораздо более простое" нормальное число приводится, для которого уж точно алгоритм понятно как писать.

(Оффтоп)

e7e5 в сообщении #299686 писал(а):

Теоретически?
Практически такую "машинку" не сыскать видно...

/dev/random