Случайность по Колмогоровуи растянутые отображения

Куда двигаться дальше для понимания случайности и ее роли в мире? Первое, что приходит в голову – нельзя ограничиваться поиском каких бы то ни было предельных значений. Поскольку все наши реальные действия конечны, а многие ограничиваются всего несколькими испытаниями или шагами, то нам нужны теории, ясно говорящие, что дает тот или иной метод за определенное число шагов. Этому посвящена часть главы 7. Другой путь – пытаться понять различие между псевдослучайностями. Ведь если, как учит алгоритмическая ТВ, имманентную случайность реально увидеть нельзя, то все наблюдаемые случайности – виды псевдослучайности. Их надо различать, а затем классифицировать. Этим мы займемся в главе 8, а здесь скажу лишь немного об одном новом подходе к оценке случайности последовательностей цифр.

Израильский математик Одед Гольдрайх[Goldreich, 1999] исходит из малой эффективности колмогоровского подхода к случайности и причин ее видит несколько. Первая – там фактически исследовалась неслучайность, так что искомый феномен выступает как предельная ситуация иного класса явлений, а не как собственно предмет исследования. Вторая – неудачно само определение случайности числа как максимальной длины задающего это число алгоритма. Третья – в данном подходе нет подлинного интереса к тому, что знают, а чего не знают о процессе случайных испытаний участники этого процесса. К сожалению, Гольдрайх, в отличие от Колмогорова, чужд проблеме обоснования ТВ, поэтому исходит из наличия вероятности у исследуемых им случайностей, однако его подход все-таки интересен для нашей темы.

Сперва Гольдрайхвводит понятие числового генератора – это алгоритм, растягивающий короткую последовательность (" цепь") нулей и единиц в гораздо более длинную цепь посредством " эффективной процедуры". Здесь очевидно следование как конструктивистам (у которых, однако, числовой генератор определялся иначе – как некое правило, преобразующее всякое натуральное n в рациональное число [Гейтинг, 1965, c. 163], т.е. в n-ое приближение к иррациональному числу), так и теории динамического хаоса, тоже изучающей растянутые отображения.

Гольдрайхназывает псевдослучайным генератор, который выдает на выходе цепь длины n, неотличимую от подлинно случайной(*) цепи той же длины n никаким вероятностным алгоритмом (из некоторого описанного им класса таких алгоритмов). Он подчеркивает, что неразличимость субъективна, поскольку зависит от класса допустимых алгоритмов и вычислительных возможностей эпохи. В качестве приемлемого псевдослучайного генератора Гольдрайхприводит программу, которая на каждом шагу возводит в квадрат результат предыдущего шага и оставляеет от полученного числа k знаков. Этот генератор давно изучен и имеет период порядка 2^2k [Иванова, 1984, с. 30-32], т.е. более миллиона шагов при k=10. Для сравнения отмечу, что квази-период числа " пи" неизвестен, но заведомо много больше ста миллионов [Шрёдер, 2001, c. 337].

Класс чисел, псевдослучайных по Гольдрайху, естественно, шире класса цепей, случайных по Колмогорову: " существуют вероятностные распределения, которые не равномерны (и даже не близки статистически к равномерному), но тем не менее неотличимые от от равномерного распределения посредством эффективной процедуры" [Goldreich, 1999, c. 1215]. Колмогоровскую случайность Гольдрайхименует онтологическим подходом (т.е. объясняющим суть явления), а свою псевдослучайность – поведенческим подходом (там же). Ему хватает своего подхода, поскольку он занят вполне определенной случайностной проблемой, которую ему задала криптография – наука о шифрах. К шифрам предъявляется требование не давать постороннему никаких статистических " зацепок", по которым он мог бы начать процедуру разгадывания шифра, т.е. текст должен выглядеть как абсолютно случайная (с точки зрения доступных на сегодня алгоритмов) цепь. С этой позиции Гольдрайхсчитает свой подход вполне успешным, хотя и признаёт саму позицию субъективной.

Итак, хотя случайность по Колмогоровуи малополезна практически, она она оказалась чрезвычайно полезна и как эталон для сравнения с иными случайностями (например, с растянутыми отображениями), и как отправной пункт для понимания природы вероятности. Однако ни один тип случайности, рассмотренный в рамках теории алгоритмов, не приблизил нас к пониманию того, откуда берется и что являет собой случайность без вероятности. К ней и надо перейти.

Глава 7. Случайность без вероятности и теория
без предельных теорем

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