Случайность по Колмогорову и растянутые отображения
Куда двигаться дальше для понимания случайности и ее роли в мире? Первое, что приходит в голову – нельзя ограничиваться поиском каких бы то ни было предельных значений. Поскольку все наши реальные действия конечны, а многие ограничиваются всего несколькими испытаниями или шагами, то нам нужны теории, ясно говорящие, что дает тот или иной метод за определенное число шагов. Этому посвящена часть главы 7. Другой путь – пытаться понять различие между псевдослучайностями. Ведь если, как учит алгоритмическая ТВ, имманентную случайность реально увидеть нельзя, то все наблюдаемые случайности – виды псевдослучайности. Их надо различать, а затем классифицировать. Этим мы займемся в главе 8, а здесь скажу лишь немного об одном новом подходе к оценке случайности последовательностей цифр.
Израильский математик Одед Гольдрайх [Goldreich, 1999] исходит из малой эффективности колмогоровского подхода к случайности и причин ее видит несколько. Первая – там фактически исследовалась неслучайность, так что искомый феномен выступает как предельная ситуация иного класса явлений, а не как собственно предмет исследования. Вторая – неудачно само определение случайности числа как максимальной длины задающего это число алгоритма. Третья – в данном подходе нет подлинного интереса к тому, что знают, а чего не знают о процессе случайных испытаний участники этого процесса. К сожалению, Гольдрайх, в отличие от Колмогорова, чужд проблеме обоснования ТВ, поэтому исходит из наличия вероятности у исследуемых им случайностей, однако его подход все-таки интересен для нашей темы.
|
|
|
Сперва Гольдрайх вводит понятие числового генератора – это алгоритм, растягивающий короткую последовательность ("цепь") нулей и единиц в гораздо более длинную цепь посредством "эффективной процедуры". Здесь очевидно следование как конструктивистам (у которых, однако, числовой генератор определялся иначе – как некое правило, преобразующее всякое натуральное n в рациональное число [Гейтинг, 1965, c. 163], т.е. в n-ое приближение к иррациональному числу), так и теории динамического хаоса, тоже изучающей растянутые отображения.
Гольдрайх называет псевдослучайным генератор, который выдает на выходе цепь длины n, неотличимую от подлинно случайной(*) цепи той же длины n никаким вероятностным алгоритмом (из некоторого описанного им класса таких алгоритмов). Он подчеркивает, что неразличимость субъективна, поскольку зависит от класса допустимых алгоритмов и вычислительных возможностей эпохи. В качестве приемлемого псевдослучайного генератора Гольдрайх приводит программу, которая на каждом шагу возводит в квадрат результат предыдущего шага и оставляеет от полученного числа k знаков. Этот генератор давно изучен и имеет период порядка 22k [Иванова, 1984, с. 30-32], т.е. более миллиона шагов при k=10. Для сравнения отмечу, что квази-период числа "пи" неизвестен, но заведомо много больше ста миллионов [Шрёдер, 2001, c. 337].
|
|
|
Класс чисел, псевдослучайных по Гольдрайху, естественно, шире класса цепей, случайных по Колмогорову: "существуют вероятностные распределения, которые не равномерны (и даже не близки статистически к равномерному), но тем не менее неотличимые от от равномерного распределения посредством эффективной процедуры" [Goldreich, 1999, c. 1215]. Колмогоровскую случайность Гольдрайх именует онтологическим подходом (т.е. объясняющим суть явления), а свою псевдослучайность – поведенческим подходом (там же). Ему хватает своего подхода, поскольку он занят вполне определенной случайностной проблемой, которую ему задала криптография – наука о шифрах. К шифрам предъявляется требование не давать постороннему никаких статистических "зацепок", по которым он мог бы начать процедуру разгадывания шифра, т.е. текст должен выглядеть как абсолютно случайная (с точки зрения доступных на сегодня алгоритмов) цепь. С этой позиции Гольдрайх считает свой подход вполне успешным, хотя и признаёт саму позицию субъективной.
|
|
|
Итак, хотя случайность по Колмогорову и малополезна практически, она она оказалась чрезвычайно полезна и как эталон для сравнения с иными случайностями (например, с растянутыми отображениями), и как отправной пункт для понимания природы вероятности. Однако ни один тип случайности, рассмотренный в рамках теории алгоритмов, не приблизил нас к пониманию того, откуда берется и что являет собой случайность без вероятности. К ней и надо перейти.
Глава 7. Случайность без вероятности и теория
без предельных теорем
Даже если вероятность удается ввести вне области стохастичности (устойчивости частот), то приходится говорить о принципиально новой вероятности – вероятности-мере, не эквивалентной вероятности-частоте. Ниже дана попытка обосновать этот тезис. Не сомневаюсь, что рано или поздно данный круг проблем привлечет внимание математиков, пока же предложу свои соображения.
Дата добавления: 2019-02-22; просмотров: 206; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!