Комментарии 13
Ай-ай-ай, воровать тележки из супермаркетов нехорошо:
Скриншот
предупрежать надо, что X конечно.
с колмогоровской сложностью — не совсем понятно. если взять реализацию как есть — бесконечную, то, я думаю, вообще невозможно построить её (реализации) алгоритмическое описание.
если же взять префикс реализации, то существует язык в котором его описание имеет длину 2.
с колмогоровской сложностью — не совсем понятно. если взять реализацию как есть — бесконечную, то, я думаю, вообще невозможно построить её (реализации) алгоритмическое описание.
если же взять префикс реализации, то существует язык в котором его описание имеет длину 2.
Колмогоровская сложность — очень теоретическая штука. Например, она невычислима…
То что вы написали про длину 2 — верно, но нету такого «языка программирования», для которого все строки длины N можно описать программами длины 2. То есть КС есть смысл рассматривать на совокупности строк, а не на одной конкретной.
То что вы написали про длину 2 — верно, но нету такого «языка программирования», для которого все строки длины N можно описать программами длины 2. То есть КС есть смысл рассматривать на совокупности строк, а не на одной конкретной.
Наверное это наивно, но я думал, что с появлением теорий хаоса, бифуркаций проблема с генерацией случайных последовательностей чисел вообще снимается… Какое-нибудь логистическое преобразование или аттрактор Лоренца разве не позволяют генерить совершенно непредсказуемые последовательности? Интересно было бы их протестировать с помощью методов, описанных в статье.
У компьютера (цифрового) конечное число состояний и переход из одного в другое строго детерминирован. Когда-нибудь мы получим такое же состояние как уже было и все следующие будут предсказуемыми, последовательность зациклится, станет периодической, а значит по определению не будет случайной.
Чисто вычислительными методами на цифровом компьютере случайную последовательность точно не получить. Максимум, можно применять вычислительные преобразования к внешним источникам энтропии, но если они реально случайные, то нет смысла и применять преобразования.
Чисто вычислительными методами на цифровом компьютере случайную последовательность точно не получить. Максимум, можно применять вычислительные преобразования к внешним источникам энтропии, но если они реально случайные, то нет смысла и применять преобразования.
Да, вы правы, я туплю… Вот, например, логистическое отображение:
При малейших изменениях параметров результат конечно сильно меняется:
lm_rand(0.5, 3.9, 100) = 0.9546
lm_rand(0.49, 3.9, 100) = 0.6160
lm_rand(0.5, 3.9, 101) = 0.1689
lm_rand(0.5, 3.91, 100) = 0.8881
Но если запускать его с теми же самыми параметрами, то результат будет один и тот же.
Насчёт зацикленности и предсказуемости не могу с вами согласиться. При определенных значениях параметра r колебания должны быть совершенно хаотическими, апериодическими. Т.е. получив скажем миллион случайных значений мы вряд ли увидим тут какую-то периодичность и не сможем по не скольким известным значениям предсказать следующие. Нужно знать алгоритм и исходные параметры.
Интересно, сделают ли когда-нибудь компьютеры, основанные на теории хаоса…
function lm_rand(x0, r, n) {
var x = x0;
for (var i = 0; i < n; i++) {
x = r * x * (1 - x);
}
return x;
}
При малейших изменениях параметров результат конечно сильно меняется:
lm_rand(0.5, 3.9, 100) = 0.9546
lm_rand(0.49, 3.9, 100) = 0.6160
lm_rand(0.5, 3.9, 101) = 0.1689
lm_rand(0.5, 3.91, 100) = 0.8881
Но если запускать его с теми же самыми параметрами, то результат будет один и тот же.
Насчёт зацикленности и предсказуемости не могу с вами согласиться. При определенных значениях параметра r колебания должны быть совершенно хаотическими, апериодическими. Т.е. получив скажем миллион случайных значений мы вряд ли увидим тут какую-то периодичность и не сможем по не скольким известным значениям предсказать следующие. Нужно знать алгоритм и исходные параметры.
Интересно, сделают ли когда-нибудь компьютеры, основанные на теории хаоса…
Т.е. получив скажем миллион случайных значений мы вряд ли увидим тут какую-то периодичность и не сможем по не скольким известным значениям предсказать следующие. Нужно знать алгоритм и исходные параметры.
Мелко плаваете — миллион. Как насчёт 2^64 (грубо — адресное пространство 64-бит процессоров) значений, например?
Хотел написать, что вы не правы, что хаос на то и хаос, что там нет никаких периодов. А человеку, который их найдёт дадут Нобелевскую премию. Но, блин, компьютеры, ведь, действительно дискретные. Если длина последовательности сравнима с точностью вычислений, то логистическое отображение однозначно начнёт повторяться. Например, если 64-битная точность вычислений, то на последовательности 2^64 однозначно будут периоды.
Кому интересно логистическое отображение, для теста нагенерил случайных чисел в Excel. Там две последовательности по 5000 значений. В них период, очевидно, не нашёл. Но на более длинных последовательностях он будет из-за ограниченной точности вычислений.
Хотя, если добавить в вычисления хотя бы текущее время, я думаю периодов можно избежать.
Кому интересно логистическое отображение, для теста нагенерил случайных чисел в Excel. Там две последовательности по 5000 значений. В них период, очевидно, не нашёл. Но на более длинных последовательностях он будет из-за ограниченной точности вычислений.
Хотя, если добавить в вычисления хотя бы текущее время, я думаю периодов можно избежать.
Дык, а собственно, в чём проблема? Сделать генератор флуктуаций, ведь, не очень сложно. Почему их не встраивают во все процессоры? Почему бы в арифметику для чисел с плавающей точкой не добавить немного случайности? Чтобы, скажем, последний разряд мог принимать действительно случайные значения.
Это конечно звучит безумно. У программистов всё должно быть абсолютно детерминировано. Но, по-моему, немного хаоса тут не помешало бы.
Это конечно звучит безумно. У программистов всё должно быть абсолютно детерминировано. Но, по-моему, немного хаоса тут не помешало бы.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Случайности не случайны?