\documentstyle[12pt,russcorr]{article}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt

\begin{document}

\centerline{СЛУЧАЙНОСТЬ}

Настоящая   работа   посвящена   изложению   ряда   попыток
определить понятие случайной последовательности.  Известные  нам
попытки   предпринимались   с   использованием   концептуального
аппарата математической логики  и  теории  алгоритмов.  В  своем
изложении мы постараемся, по возможности,  следовать  внутренней
логике  предмета,  привлекая  различные   интуитивные   описания
свойств случайности. Ряд базисных понятий алгоритмической теории
сложности и случайности объясняются в приложении 1  к  настоящей
работе.

Подход   с   позиций   теории   алгоритмов    обуславливает
определенную специфику большинства обсуждаемых результатов.  Эта
специфика видна, скажем, на  следующем  примере:  если  изменить
непрерывную функцию в конечном числе точек, она  перестает  быть
непрерывной, если то же проделать  с  вычислимой  функцией,  она
остается  вычислимой.  Феномен,  лежащий  в  основе  предыдущего
примера,  выявляется  и  при  попытке  приписать  количественную
характеристику  индивидуальному  (конечному)  объекту  в  теории
алгоритмов. Такое приписывание оказывается содержательным будучи
применяемым  к  бесконечной  совокупности  (конечных)  объектов,
характеристика же одного  объекта  оказывается  определяемой  ``с
точностью'' до аддитивной  константы,  что  выглядит  парадоксом,
если не нонсенсом.

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

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

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

\centerline{Источники представления о случайности}

Разрабатывая философские  представления  о  случайности  мы
пытаемся  исходить  из  нашего  (и   общечеловеческого)   опыта.
Разумеется,   в   этом   опыте   встречались   только   конечные
последовательности.  Схемы  наших  построений,  таким   образом,
состоят  в  том,  чтобы  используя  наш  опыт  о  конечном  мире
осуществить в соответствии с общематематической  традицией  (ср.\
геометрию)  построения   в   мире   бесконечности.   Результаты,
полученные  в  бесконечном  мире,  можно  после  этого  пытаться
адаптировать  к  конечному.  Итак,  мы  будем   развертывать   и
формализовывать следующие два  свойства  ``интуитивно  случайных''
последовательностей:

1.~Случайную    последовательность    нельзя    предугадать
(предвидеть, предсказать) даже пронаблюдав ее начало.  Случайная
последовательность не закономерна.

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

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

\centerline{Закономерности}

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

ОБОЗНАЧЕНИЕ.  Множество    всех    (двоичных)    конечных
последовательностей обозначим $\Xi $, множество всех бесконечных --- $\Omega $,
через $\Omega_{x}$  обозначим  множество  всех  бесконечных   продолжений
конечной последовательности $x$.

ОПРЕДЕЛЕНИЕ. Закономерность --- это произвольное  отображение
из $\Xi $ в $2^{\Xi }$.

ОПРЕДЕЛЕНИЕ. Последовательность $\omega $  из $\Omega $   удовлетворяет
закономерности $f$, если  для  всякого  конечного $x$  ---  начала $\omega $
выполнено:

$xf(x)$ содержит некоторое начало последовательности $\omega $.  Если
к тому же для всякого конечного $x$ --- начала $\omega $,  множество $f(x)\Omega $
отлично  от $\Omega $,  мы  будем   говорить   что   закономерность $f$
нетривиальна на $\omega $.

ОПРЕДЕЛЕНИЕ. Последовательность   беззаконна,   если   не
существует закономерности, нетривиальной на ней.

ОПРЕДЕЛЕНИЕ. Последовательность $\omega \in \Omega $ закономерна,  если  она
удовлетворяет некоторой закономерности, нетривиальной на ней.

ЗАМЕЧАНИЕ.  Мы   могли   бы   модифицировать   определение
закономерности,  потребовав   нетривиальности $f$   только   для
бесконечного  количества  начал $\Omega $.  Это,  однако,  приведет   к
равнообъемному определению.

Несложно получить характеризацию закономерности в  терминах
эффективных топологических пространств.

Напомним,  что  на   множестве $\Omega $   имеется   каноническая
топология, базой которой являются все множества вида $\Omega _{x}$.\footnote{В приложении 1.}
Среди всех   открытых   множеств   выделяются   эффективно   открытые,
являющиеся объединением последовательностей $\Omega _{x_{n}}$, для  вычислимых
последовательностей $x_{n}$.\footnote{В приложении 1.}

Наши   определения    нетривиальной
закономерности  можно  трансформировать  так,   чтобы   функция,
аналогичная $f$, назовем ее $g$, давала бы по $x$ ---  началу $\omega $,  такую
последовательность $g(x)$, что $xg(x)$ не является началом $\omega $.

ТЕОРЕМА. {\it Закономерная последовательность --- это  в  точности
граничные точки эффективно открытых множеств.}

ДОКАЗАТЕЛЬСТВО.  Пусть  дана  ``закономерность $g$,   дающая
не-начала $xg(x)$''.  Тогда  объединение  множеств  вида $\Omega _{xg(x)}$  ---
эффективно открыто, не  содержит $\omega $,  но  пересекается  с  любой
окрестностью $\omega $ (т.е.\ множеством вида $\Omega _{x}$, $x$ --- начало $\omega $).

Обратно, пусть $\omega $ --- граничная точка объединения $\Omega _{z}$,  где $z$
пробегает перечислимое множество $A$.  Поскольку $\omega $  ---  граничная
точка, для всякого  начала $x$  можно  дождаться  появления  в $A$
элемента    вида $xy$.    Это $y$    и    объявим    значением
закономерности не-продолжения для $x$. Теорема доказана.

Поскольку множество граничных точек открытого множества  (в
нашем пространстве)  негде  не  плотно,  а  эффективно  открытых
множеств счетное число, мы получаем следствие.

СЛЕДСТВИЕ.  {\it Закономерные    последовательности    образуют
множество первой категории.}

Таким  образом,  беззаконных  последовательностей  много  в
смысле категории.
Соответствует    ли    наше     определение     беззаконной
последовательности второму из наших  интуитивных  свойств,  т.е.\
являются  ли  последовательности,  получающиеся   при   бросании
монеты, беззаконными?

Само  слово  ``беззаконный''  наводит  на  мысль  о  проверке
обычных   законов   теории    вероятностей    для    беззаконных
последовательностей.  Результат   такой   проверки   оказывается
неутешительным с точки зрения попытки  отождествить  интуитивную
случайность с формальной беззаконностью.

ТЕОРЕМА. {\it Всякая последовательность, удовлетворяющая  закону
больших чисел, закономерна.}

Доказательство состоит  просто  в  переформулировке  закона
больших чисел в форме закономерности нашего типа.  Для  простоты
рассмотрим    случай     равномерного     распределения.     Для
последовательности, доля  единиц  в  которой  стремится  к  $1/2$,
найдется такая длина ее начального отрезка $N$, что для всех более
длинных отрезков доля единиц в них превосходит $1/3$. Но  то,  что
сейчас  сформулировано,   и   есть   нетривиальная   для   нашей
последовательности закономерность --- для отрезков  короче $N$  она
дает просто очередной бит, для остальных  отрезков  ---  исключает
какое-нибудь одно продолжение, в котором доля единиц меньше $1/3$.
Теорема доказана.

Мы взяли  в  качестве  источника  закономерности  (в  нашем
смысле) закон больших чисел. Читателю,  вероятно,  ясно,  что  к
аналогичному результату привели бы и другие классические  законы
теории вероятностей.

Есть еще одно соображение, показывающее, что  наше  понятие
беззакония априори не годится как уточнение понятия случайности.
Дело в том, что это определение должно зависеть от распределения
вероятностей, и невозможность  предугадывать  последовательность
должна  означать  невозможность  получить  в  результате  такого
предугадывания   пользу   большую,   чем   гарантируют    знание
распределения.

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

Встречаются ли беззаконные  последовательности  в  природе?
Скорее всего --- нет. По крайней мере  их  появление  имело  бы  в
качестве  неприятного   последствия   возникновение   физических
законов, ``подтверждаемых многовековой историей человечества''  (и
даже вселенной) и внезапно нарушаемых.

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

\centerline{Частотной подход к определению случайности}

Закон больших чисел, к которому мы уже обращались  в  нашем
рассмотрении,   конечно   занимает   особое   место   в   теории
вероятностей.  Он  являлся  исторически  первым  и  по  существу
формализует  исходное  интуитивное  понятие   вероятностей.   Не
удивительно, что первая попытка формализовать понятия  случайной
последовательности эксплуатировала именно этот закон,  апеллируя
ко   второму   из   зафиксированных   нами   свойств   случайных
последовательностей. Попытка эта принадлежит фон Мизесу.

Попытаемся выработать определение случайности, базирующееся
на ЗБЧ и  удовлетворяющее  нашей  интуиции.  Потребовать  просто
выполнености ЗБЧ слишком мало --- последовательность  010101  вряд
ли назовешь случайной. Идея Мизеса состояла в  рассмотрении  ЗБЧ
для подпоследовательностей. Конечно,  рассматривать  просто  все
подпоследовательности тоже бессмысленно --- требование оказывается
слишком сильным --- ведь можно взять подпоследовательность  просто
из равных нулю членов. Так что взятие  члена  последовательности
не должно зависеть от  его  значения  даже  косвенно,  например,
правило выбора ``брать член, если перед ним и  после  него  стоит
ноль''   тоже   не   годится.    С    другой    стороны,    выбор
подпоследовательности    с    возрастающими    номерами    (т.е.\
подпоследовательности в  обычном  смысле)  не  выглядит  априори
очевидным   ограничением,   подпоследовательности    могли    бы
выбираться и ``немонотонно''.

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

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

Итак, наша  последовательность  ---  это  бесконечная  колода
карт, на лицевой стороне которых написан 0 или 1, а на рубашке ---
номер по порядку. Правило  выбора  подпоследовательности  ---  это
алгоритм, который получает на вход все уже перевернутые карты  и
указывает, какую следующую карту перевернуть, а также, войдет ли
эта карта в формируемую  подпоследовательность  (таким  образом,
карту можно ``посмотреть, но не брать'').

ОПРЕДЕЛЕНИЕ. Последовательность называется  стохастической,
если  любое  правило  выбора  дает  ее  подпоследовательность  с
частотой единиц стремящейся к $1/2$.

Данное определение можно обобщать и на случай неравномерных
распределений.

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

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

Мы  предлагаем   следующее   уточнение   понятия   ``слишком
различные  распределения''  из  приведенной   выше   формулировки
принципа различения.

ОПРЕДЕЛЕНИЕ. Две меры называются взаимно сингулярными, если
существует множество меры 0 относительно одной из них  и  полной
меры относительно другой.

ПРИНЦИП РАЗЛИЧЕНИЯ. Не   существует   последовательности,
случайной относительно двух взаимно сингулярных распределений.

Рассмотрим теперь класс вычислимых вероятностных процессов,
предложенных  Ламбальгеном.  Процесс  такого  класса  состоит  в
последовательности  независисых  бросаний   монет   с   различой
вероятностью $p(n)$ выпадения герба при бросании $n$-ой монеты.

Как  показывает   следующая   теорема,   наше   определение
стохастичности ``склеивает'' разные процессы Ламбальгена.

ТЕОРЕМА (Шень).  {\it Пусть в процессе Ламбальгена $p(n)\longrightarrow 1/2$.
Тогда  стохастические  последовательности   образуют   множество
полной  меры  относительно   распределения,   задаваемого   этим
процессом.}

ТЕОРЕМА (Какутани). {\it Пусть  для  процесса  Ламбальгена  ряд
$\sum (p(n)-1/2)^{2}$ расходится. Тогда мера, отвечающая этому  процессу,
и равномерная мера взаимно сингулярны.}\footnote{Последний абзац п.6.4 нужно переписать  полностью $\langle$А.С.$\rangle$}

Сделаем еще одно замечание  к  понятию  стохастичности.  На
первый взгляд кажется, что подпоследовательность, получаемая  из
исходной  по  правилу  выбора,  ничуть  не  хуже   исходной,   в
частности, если исходная была стохастичной, то  и  новая  будет.
Другими словами, можно рассмотривать последовательное применение
двух  правил  выбора.  Однако,  более   детальное   рассмотрение
показывает, что последовательное  применение  может  привести  к
результату, означающему, что в решении вопроса о взятии  или  не
взятии  некоей  карты  косвенно  учитывается  ее  значение.  Это
подрывает как саму идею композиции, так и, в некоторой  степени,
определения стохастичности в качестве аналога случайности.

Итак,    понятие    стохастичности    безусловно    отражая
определенные черты понятия случайности все же слишком широко.  В
дальнейшем расссмотрении  мы  будем  искать  понятия  во-первых,
более узкие, во-вторых, все еще задающие множества меры 1.

\centerline{Игровой подход}

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

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

Ограничимся на некоторое время равномерным распределением.

Итак, в нашей Игре  имеется  два  противника  ---  Человек  и
Казино.  В  начальный  момент  времени  каждый  из   противников
обладает некоторым капиталом (вообще говоря, различным). В  игре
участвует  упоминавшаяся  выше  колода  карт.  (Мы  интересуемся
случайностью  последовательности,  изображаемой  этой  колодой.)
Человек в очередной момент игры указывает  на  еще  не  открытую
карту,  называет  значение  карты  и  ставку,  не  превосходящую
имеющейся у него в этот момент суммы денег.  После  этого  карта
открывается и названная сумма  денег  переходит  от  Человека  к
Казино, если Человек не угадал, и от  Казино  к  Человеку,  если
Человек угадал. Если Человек угадал, но последнее невозможно, то
Казино разорилось. Ясно, что можно  считать  (и  мы  так и будем
делать), что начальный капитал Человека равен 1.

Данное  определение  было  дано  для  случая   равномерного
распределения  вероятностей  на  двоичных   последовательностях.
Однако   его   легко   модифицировать,   предполагая,   что   на
пространстве   всех    двоичных    последовательностей    задана
произвольная мера, не равная 0 на непустых открытых  множествах.
При этом правило выплаты выигрыша/проигрыша должно  быть  таким,
чтобы  математическое  ожидание   (относительно   данной   меры)
выигрыша на каждом шаге было равно 0.

Мы  готовы  дать  теперь  очередное,   предлагаемое   нами,
определение случайности. Как это бывало и  раньше,  его  удобнее
дать в форме не-случайности.

ОПРЕДЕЛЕНИЕ.  Пусть  дано   вычислимое   распределение   на
пространстве  двоичных  последовательностей.  Последовательность
\underline{предсказуема} относительно этого распределения, если при Игре  на
этой последовательности Человек имеет  вычислимую  стратегию  (с
рациональными  ставками), разоряющую  Казино   при   любом   его
начальном капитале.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Посмотрим, как обстоит дело с желанными для нас  свойствами
случайности.

ТЕОРЕМА.  {\it Множество   последовательностей,  непредсказуемых
относительно данного распределения, имеет меру  1  (относительно
него же).}

ТЕОРЕМА.  {\it Все  непредсказуемые   относительно  равномерного
распределения последовательности стохастичны.}

Понятие непредсказуемости лучше ведет себя по  отношению  к
нашему принципу различения, чем понятие стохастичности.

ТЕОРЕМА. {Пусть для процесса  Ламбальгена  ряд $\sum (p(n)-1/2)^{2}$
расходится. Тогда почти  все  в  смысле  меры,  задаваемой  этим
процессом, последовательности одновременно:}

1) {непредсказуемы относительно равномерной меры}

2) {стохастичны}

\centerline{Конечный случай.~I}

Как  это  часто  бывает,  в  конечном  случае  бессмысленно
говорить о случайности/неслучайности. Разумно говорить о большей
или  меньшей  степени  случайности.  Попытаемся   сделать   это,
перенеся  на   конечный   случай   наше   игровое   определение.
Количественность подхода выражается, в частности, в том, что  мы
начнем дифференцировать  стратегии  Человека  по  их  сложности.
Уточнением понятия сложности мы займемся  несколько  позднее,  а
пока можно ограничиться интуитивным представлением  о  сложности
стратегии, как о длине кратчайшего описания этой стратегии.

Для  простоты  мы  начнем  наше  рассмотрение   со   случая
равномерной меры (для которого и было  полностью  сформулировано
понятие Игры в бесконечном случае).

ОПРЕДЕЛЕНИЕ.     Конечная           последовательность
$(\alpha,\beta)$-предсказуема,   если   существует   стратегия    Человека,
сложность которой меньше $\alpha $, разоряющая Казино с капиталом $2^{\beta }$.

Отметим, что в наших условиях, если Человек откуда-то узнал
первые $\beta $ карт колоды, то  он  располагает  стратегией, сложность
которой при естественном определении не превосходит  существенно
$\beta $ и позволяет ему выиграть $2^{\beta }$.

Понятие сложности конечного объекта как минимальной  длины
его описания было введено  Колмогоровым  и  допускает  различные
уточнения, адекватные в тех или иных ситуациях.

Сейчас  мы  дадим  систему  определений,  которая  наиболее
удобна для наших целей. Пусть $f(p,y)$ --- любая вычислимая функция,
$p$, $y$ --- двоичные слова, $l$ --- длина слова. Тогда
$$
K_{f}(x\mid y)=\min_{l(p)}\{p\mid f(p,y)=x\}
$$

Как и для других сложностей, среди $f$  имеется  оптимальная
функция $u$, где
$$
\forall f\,\exists c\,\forall x,y\ K_{u}(x\mid y)\le K_{f}(x\mid y)+c
$$

Зафиксируем любую такую $f$ и будем обозначать $K_{f}$ через $K$.  В
действительности, $f$ может быть выбрана очень  даже  естественной
(см. [Левин]), но мы сейчас не будем в это вдаваться.\footnote{Это место переработать в соответствии с замечанием А.Мучника.}

Возвращаясь к  определению  $(\alpha,\beta)$-предсказуемости  конечной
последовательности   мы   предлагаем   в   качестве    сложности
использовать\\
$K(\cdot\mid$ длина последовательности). В  дальнейшем  под
сложностью всюду будет пониматься определенная сейчас.\footnote{Проверить!}

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

ОПРЕДЕЛЕНИЕ. Конечная последовательность $x$ $\alpha$-хаотична, если
ее сложность превосходит $l(x)-\alpha$.

ТЕОРЕМА. {\it Доля $\alpha$-нехаотичных    последовательностей    не
превосходит $2^{-\alpha}$.}\footnote{Надо бы упорядочить  терминологию  с  мерой,  распределением  и
вычислимым   распределением,   etc.\ и   дать   определения   в
приложении 1. Определить там же ${\rm lb}(n)$, сложность,\ldots}

Как и в бесконечном случае  можно  установить  связь  между
предсказуемостью и хаотичностью.

ТЕОРЕМА.  {\it Если      последовательность     длины $n$
$(\alpha,\beta)$-предсказуема, то она не $(\beta-\alpha-c{\rm lb}\,n)$-хаотична.}\footnote{Доказательство.}

В формулировке предыдущей теоремы имелся аддитивный член $c{\rm lb}\,n$,
обычный для утверждений колмогоровской теории сложности.

В нашем определении предсказуемости для бесконечного случая
фигурировала   вычислимая   стратегия   ---   стратегия \underline{конечной}
(разумеется) сложности. В конечном случае и в смысле формального
переноса  с  бесконечного,  и  по  содержательным   соображениям
естественно  считать,  что  сложность  стратегии $\alpha $  существенно
меньше $n$, скажем меньше $2{\rm lb}\,n$. В то же время, например, выигрыш $\beta $
может быть очень большим и определять ``степень предсказуемости''.
При этом, в зависимости от дополнительных  обстоятельств,  может
оказаться разумным  иначе  определять  степень  предсказуемости,
например, как $\beta/\alpha$.

\centerline{Хаотичность}

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

ОПРЕДЕЛЕНИЕ.  Последовательность   хаотична,   если    для
некоторого $c$ сложность всякого ее начала превосходит длину этого
начала минус $c$.

Здесь мы, как вы видите, не зафиксировали никакого  понятия
сложности. Простейшая сложность $K(x)=\min(l(p)\mid n(p)=x)$, здесь  не
годится (класс, задаваемый определением, оказывается пустым).

Однако имеется один из вариантов понятия сложности,  идейно
весьма тесно связанный  с  исходной  идеей  Колмогорова,  однако
формально весьма далекий от того, который  нам  подходит.  Чтобы
определить  нужные  понятия,  дадим  кое-какие   вспомогательные
определения.\footnote{Дать определение.}

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

ТЕОРЕМА.  {\it Почти   все   (в   смысле   равномерной    меры)
последовательности хаотичны.}

ТЕОРЕМА.  {\it Хаотичность  влечет  стохастичность (относительно
равномерной меры).}

Насколько  сильно   различаются   понятия   хаотичности   и
стохастичности? Следующая теорема показывает,  что  с  некоторой
``практической точки'' зрения они почти неразличимы.\footnote{Теорема (Мучник) $\langle$буквально 10.5.2$\rangle\langle$Доказательство$\rangle$}

Сравним теперь хаотичность с непредсказуемостью.

ТЕОРЕМА. {\it Хаотичность влечет непредсказуемость (относительно
равномерной меры).}\footnote{Теорема 10.6.2}

ОТКРЫТАЯ ПРОБЛЕМА.  Равносильны    ли    хаотичность    и
непредсказуемость?

Другими словами можно ли  из  всякой  не-сложности  извлечь
практическую выгоду (в форме выигрыша)?

Рассмотрим теперь случай произвольной вычислимой меры.  Как
мы помним (см. ...), мера задана на  интервалах  (конусах)  вида
$\Omega_{x}$. Мы будем часто говорить вместо меры $\Omega _{x}$ о мере $x$.\footnote{В приложении 1}

ОПРЕДЕЛЕНИЕ. Последовательность хаотична (по мере $p$)  если
отношение априорной полумеры всякого  ее  начала  к  мере  этого
начала ограничено.

(Конечно, это определение  переходит  в  вышеприведенное  в
случае равномерной меры.)

ОПРЕДЕЛЕНИЕ. Последовательность назовем природной, если она
хаотична по какой-либо вычислимой мере.

Термин природная здесь имеет для  нас  определенный  смысл.
Заметим в его пользу, что всякая  вычислимая  последовательность
оказывается  природной.  (Она  хаотична  по   вычислимой   мере,
сосредоточенной на ней.) Еще одно соображение в  пользу  термина
(и  его  философской  концепции)  состоит   во   взаимоотношении
беззаконности и природности.

ТЕОРЕМА. {\it Беззаконные последовательности не природны.}

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

Вышеприведенный комментарий о близости непредсказуемости  и
хаотичности находит еще одно подтверждение в следующей теореме.

Теорема~11,4\footnote{Включить ссылки на меры.}

В то же время стохастичность, хотя, как было установлено  в
Т..., ``количественно'' близка к непредсказуемости (и хаотичности),
но все же отличается от них и от природных последовательностей.\footnote{Теорема 11.5}

\centerline{Конечные последовательности. II}

В  настоящем  разделе  мы  рассматриваем  случай   конечных
последовательностей.

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

ОПРЕДЕЛЕНИЕ. Последовательность $\beta $-хаотична,  если  ее  мера
больше ее априорной полумеры, деленной на $2^{\beta}$.\footnote{Здесь вместо  априорной  полумеры  может  быть  разумнее  брать
другую функцию, предлагаемую Ан.Мучником ---  эта  функция  бывает
безусловной или условной (от  двух  аргументов),  полувычислимой
(снизу), с  условием  нормировки:  сумма  ее  значений  на  всех
последовательностях   произвольной   фиксированной   длины    не
превосходит единицы, и условием максимальности.}

Наше  определение  совпадает  с   приведенным   в   разделе
Конечные последовательности. I определением $\beta $-хаотичности  для
равномерной меры.

Если  нам  заранее  известна  фиксированная  мера,   то   в
предыдущем определении разумно говорить  об  априорной  полумере
относительно  известной  меры  (задание  которой  есть  конечный
объект).

С  другой  стороны,  возможна  и   ситуация,   когда   мера
неизвестна и  мы  ищем  простейшую  меру,  относительно  которой
заданная последовательность случайна, в этом  случае  осмысленно
рассматривать    априорную    полумеру    относительно     длины
последовательности.

В  самый  последний  период  своей   научной   деятельности
А.Н.Колмогоров поставил перед своими учениками  задачу  изучения
меры  случайности  конечных  последовательностей.   Предложенный
Колмогоровым способ определения соответствующего  понятия  может
быть формализован в следующем виде.

Рассмотрения Колмогорова, по видимому, также были связаны
с тезисом, в соответствии с  которым  всякая  последовательность
возникающая в каком-то природном процессе, случайна относительно
подходящей вычислимой меры, см. выше.\footnote{М.б.  более   подробный   рассказ   о   Колмогорове   перенести
куда-нибудь еще.}

ОПРЕДЕЛЕНИЕ. Последовательность $(\alpha,\beta)$-природна, если   она
$\beta $-хаотична, относительно некоторой (конечной) меры сложности, не
превосходящей $\alpha $.

Естественный вопрос,  сформулированный  А.Н.Колмогоровым  в
связи с этим определением, состоит в том, существуют  ли  вообще
(в      метаматематическом       смысле)       $(\alpha,\beta)$-неприродные
последовательности при естественных ограничениях на $\alpha $ и $\beta $.

Как   показал   Шень,   они    существуют,    доля    таких
последовательностей  была  оценена  Вьюгиным.  Наиболее   точный
результат в этом направлении принадлежит Ан.Мучнику.

ТЕОРЕМА

Можно рассмотреть комбинацию подходов настоящего раздела  и
раздела Случайность конечных  последовательностей. I,  другими
словами, использовать понятия игры и  предсказуемости.  Тогда  в
нашем  определении  появится  еще  один  параметр  ---   сложность
стратегии.\footnote{п.п.13,14 пишет Горбунов с Мучником.}

Завершим  нашу  работу  простым  парадоксом,   к   которому
приводит изложенная в ней система понятий.

В  соответствии  с   нашей   философией   не   все   бесконечные
последовательности могут возникать в природе. С другой  стороны,
случайные  ---  могут,  и  всякая  последовательность,  вычислимая
относительно  некоторой  возникающей  в  природе,  также   может
возникнуть.   Но,   как   показал   Гач,   всякая    бесконечная
последовательность вычислима относительно некоторой  хаотической
(по равномерной мере)!

\end{document}

