Алгоритмически случайная последовательность

«Алгоритмическая случайность» перенаправляется сюда. Не путать со рандомизированными алгоритмами .

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

В теоретико-мерной теории вероятностей , предложенной Андреем Колмогоровым в 1933 году, не существует такого понятия , как случайная последовательность. Например, рассмотрим подбрасывание честной монеты бесконечное количество раз. Любая конкретная последовательность, будь то $0000\dots$ или $011010\dots$, имеет равную вероятность, равную ровно нулю. Невозможно утверждать, что одна последовательность «более случайна», чем другая, используя язык теории вероятности. Однако интуитивно очевидно, что $011010\dots$ выглядит более случайным, чем $0000\dots$. Алгоритмическая теория случайности формализует эту интуицию.

Поскольку иногда рассматриваются различные типы алгоритмов, начиная от алгоритмов с конкретными ограничениями времени их работы и заканчивая алгоритмами, которые могут задавать вопросы машине-оракулу , существуют разные понятия случайности. Наиболее распространенная из них известна как случайность Мартина-Лёфа ( K-случайность или 1-случайность ), но существуют также более сильные и слабые формы случайности. Когда термин «алгоритмически случайный» используется для обозначения конкретной одиночной (конечной или бесконечной) последовательности без пояснений, под ним обычно понимают «несжимаемую» или, в случае, если последовательность бесконечна, с префиксом алгоритмически случайной (т. е. K -несжимаемая), «случайность Мартина-Лёфа-Чайтина».

Было показано, что с момента своего создания случайность Мартина-Лёфа допускает множество эквивалентных характеристик — с точки зрения сжатия , тестов на случайность и азартных игр — которые внешне мало похожи на исходное определение, но каждая из которых удовлетворяет нашему интуитивному представлению о свойствах, которые случайны. Последовательности должны иметь: случайные последовательности должны быть несжимаемыми, они должны проходить статистические тесты на случайность, и на них должно быть трудно зарабатывать деньги . Существование этих многочисленных определений случайности Мартина-Лёфа и стабильность этих определений при различных моделях вычислений свидетельствуют о том, что случайность Мартина-Лёфа является фундаментальным свойством математики, а не случайностью конкретной модели Мартина-Лёфа.

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

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

Класс всех случайных (бинарных) последовательностей Мартина-Лёфа обозначается RAND или MLR.

История

Рихард фон Мизес

Рихард фон Мизес формализовал понятие теста на случайность , чтобы определить случайную последовательность как последовательность, которая прошла все тесты на случайность. Он определил «коллектив» ( коллектив ) как бесконечную двоичную строку. $x_{1:\infty }$ определено так, что

• Существует предел $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{i}=p\in (0,1)$.
• Для любого «допустимого» правила, такого, что оно выделяет бесконечную подпоследовательность $(x_{m_{i}})_{i}$ из строки у нас все еще есть $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$. Он назвал этот принцип « невозможностью игорной системы ».

Чтобы выбрать подпоследовательность, сначала выберите двоичную функцию $\phi$, такой, что для любой двоичной строки $x_{1:k}$, он выводит либо 0, либо 1. Если он выводит 1, то мы добавляем $x_{k+1}$ к подпоследовательности, иначе продолжим. В этом определении некоторые допустимые правила могут навсегда воздерживаться от некоторых последовательностей и, таким образом, не смогут выделить бесконечную подпоследовательность. Мы рассматриваем только те, которые выбирают бесконечную подпоследовательность.

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

Определение обобщает двоичный алфавит на счетный алфавит:

• Частота каждой буквы сходится к пределу больше нуля.
• Для любого «допустимого» правила, такого, что оно выделяет бесконечную подпоследовательность $(x_{m_{i}})_{i}$ из строки частота каждой буквы в подпоследовательности по-прежнему сходится к тому же пределу.

Обычно допустимые правила определяются как правила, вычислимые машиной Тьюринга, и мы требуем $p=1/2$. При этом мы имеем случайные последовательности Мизеса-Вальда-Черча . Это не является ограничением, поскольку задана последовательность с $p=1/2$, мы можем построить случайные последовательности с любыми другими вычислимыми $p\in (0,1)$. Здесь «Черч» относится к Алонсо Чёрчу , чья статья 1940 года предлагала использовать вычислимые по Тьюрингу правила.

Теорема. ( Абрахам Вальд , 1936, 1937) Если допустимых правил только счетное число, то почти любая последовательность является коллективной.

Схема доказательства: используйте теоретико-мерную вероятность.

Зафиксируйте одно допустимое правило. Выберите случайную последовательность из пространства Бернулли. С вероятностью 1 (используйте мартингалы) подпоследовательность, выбранная допустимым правилом, все еще имеет $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$. Теперь добавим все счетное число правил. С вероятностью 1 каждая подпоследовательность, выбранная каждым правилом, по-прежнему имеет $\lim _{n}{\frac {1}{n}}\sum _{i=1}^{n}x_{m_{i}}=p$.

Контрпример. (Жан Виль, 1939) Если допустимых правил только счетное число, то существует коллектив с ${\frac {1}{n}}\sum _{k=1}^{n}x_{k}\geq p$ для всех $n$.

Доказательство: См.

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

Пер Мартин-Лёф

Контрпример Вилле предполагает, что ощущение случайности Мизеса-Вальда-Черча недостаточно хорошо, поскольку некоторые случайные последовательности не удовлетворяют некоторым законам случайности. Например, контрпример Вилле не удовлетворяет одному из законов повторного логарифма :

$$\limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1$$

Наивно это можно исправить, потребовав, чтобы последовательность удовлетворяла всем возможным законам случайности, где «закон случайности» — это свойство, которому удовлетворяют все последовательности с вероятностью 1. Однако для каждой бесконечной последовательности $y_{1:\infty }\in 2^{\mathbb {N} }$, у нас есть закон случайности, который $x_{1:\infty }\neq y_{1:\infty }$, что приводит к выводу об отсутствии случайных последовательностей.

( Пер Мартин-Лёф , 1966) определил «случайность Мартина-Лёфа», допуская только законы случайности, вычислимые по Тьюрингу. Другими словами, последовательность является случайной тогда и только тогда, когда она проходит все вычислимые по Тьюрингу тесты случайности.

Тезис о том, что определение случайности Мартина-Лёфа «правильно» отражает интуитивное понятие случайности, был назван тезисом Мартина-Лёфа-Чайтина ; это чем-то похоже на тезис Чёрча-Тьюринга .

Диссертация Мартина-Лёфа-Чайтина. Математическая концепция «случайности Мартина-Лёфа» отражает интуитивное представление о том, что бесконечная последовательность является «случайной». Тезис Чёрча-Тьюринга. Математическая концепция «вычислимости на машинах Тьюринга» отражает интуитивное представление о «вычислимости» функции.

Подобно тому, как вычислимость по Тьюрингу имеет множество эквивалентных определений, случайность Мартина-Лёфа также имеет множество эквивалентных определений. См. следующий раздел.

Три эквивалентных определения

Первоначальное определение случайной последовательности, данное Мартином-Лёфом, основывалось на конструктивных нулевых покрытиях; он определил последовательность как случайную, если она не содержится ни в одном таком покрытии. Грегори Чайтин , Леонид Левин и Клаус-Питер Шнорр доказали характеристику с точки зрения алгоритмической сложности : последовательность является случайной, если существует равномерная граница сжимаемости ее начальных сегментов. Шнорр дал третье эквивалентное определение в терминах мартингалов . Книга Ли и Витани «Введение в колмогоровскую сложность и ее приложения» представляет собой стандартное введение в эти идеи.

• Алгоритмическая сложность (Chaitin 1969, Schnorr 1973, Levin 1973): Алгоритмическую сложность (также известную как (беспрефиксная) колмогоровская сложность или сложность размера программы) можно рассматривать как нижнюю границу алгоритмической сжимаемости конечной последовательности (из символы или двоичные цифры). присваивается Каждой такой последовательности w натуральное число K(w), которое интуитивно измеряет минимальную длину компьютерной программы (написанной на каком-то фиксированном языке программирования), которая не принимает никаких входных данных и выводит w при запуске. Сложность должна быть свободной от префиксов: за программой (последовательностью 0 и 1) следует бесконечная строка нулей, а длина программы (при условии, что она остановлена) включает количество нулей справа от Программа, которую читает универсальная машина Тьюринга. Дополнительное требование необходимо, поскольку мы можем выбрать такую ​​длину, чтобы она кодировала информацию о подстроке. Учитывая натуральное число c и последовательность w , мы говорим, что w является c -несжимаемым, если $K(w)\geq |w|-c$.

Бесконечная последовательность S является случайной по Мартину-Лёфу тогда и только тогда, когда существует константа c все S конечные такая, что префиксы являются c -несжимаемыми. Более кратко, $K(w)\geq |w|-O(1)$.

• Конструктивные нулевые покрытия (Мартин-Лёф, 1966): это оригинальное определение Мартина-Лёфа. Для конечной двоичной строки w мы C _w обозначим цилиндр, порожденный w . Это набор всех бесконечных последовательностей, начинающихся с w , который является базовым открытым множеством в канторовом пространстве . Мера произведения w µ( C _w ) цилиндра, порожденного , определяется как 2 ^{−| в |} . Каждое открытое подмножество канторова пространства представляет собой объединение счетной последовательности непересекающихся основных открытых множеств, а мера открытого множества — это сумма мер любой такой последовательности. Эффективное открытое множество — это открытое множество, которое представляет собой объединение последовательности базовых открытых множеств, определяемой рекурсивно перечислимой последовательностью двоичных строк. Конструктивное нулевое покрытие или эффективной меры 0 набор представляет собой рекурсивно перечислимую последовательность. $U_{i}$ эффективных открытых множеств таких, что $U_{i+1}\subseteq U_{i}$ и $\mu (U_{i})\leq 2^{-i}$ для каждого натурального числа i . Каждое эффективное нулевое покрытие определяет $G_{\delta }$ множество меры 0, а именно пересечение множеств $U_{i}$.

Последовательность считается случайной по Мартину-Лёфу, если она не содержится ни в одном из $G_{\delta }$ множество, определяемое конструктивным нулевым покрытием.

• Конструктивные мартингалы (Шнорр, 1971): Мартингал — это функция. $d:\{0,1\}^{*}\to [0,\infty )$ такой, что для всех конечных строк w , $d(w)=(d(w^{\smallfrown }0)+d(w^{\smallfrown }1))/2$, где $a^{\smallfrown }b$ — это объединение строк a и b . Это называется «условием справедливости»: если мартингейл рассматривается как стратегия ставок, то вышеуказанное условие требует, чтобы игрок играл с честными коэффициентами. мартингал d Говорят, что успешен в последовательности S , если $\limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,$ где $S\upharpoonright n$ это первые n битов S. — Мартингал d является конструктивным (также известным как слабо вычислимый , полувычислимый снизу ), если существует вычислимая функция ${\widehat {d}}:\{0,1\}^{*}\times \mathbb {N} \to {\mathbb {Q} }$ такая, что для всех конечных двоичных строк w

1. ${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ для всех положительных целых чисел t ,
2. $\lim _{t\to \infty }{\widehat {d}}(w,t)=d(w).$

Последовательность является случайной по Мартину-Лёфу тогда и только тогда, когда ни один конструктивный мартингал на ней не удается.

Интерпретации определений

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

Характеристика нулевого покрытия дает интуитивное представление о том, что случайное действительное число не должно иметь каких-либо «необычных» свойств. Каждый набор мер 0 можно рассматривать как необычное свойство. Невозможно, чтобы последовательность не принадлежала множествам с мерой 0, потому что каждое одноточечное множество имеет меру 0. Идея Мартина-Лёфа заключалась в том, чтобы ограничить определение измерениями 0 множеств, которые эффективно описуемы; определение эффективного нулевого покрытия определяет счетную коллекцию эффективно описываемых множеств меры 0 и определяет последовательность как случайную, если она не лежит ни в одном из этих конкретных множеств меры 0. Поскольку объединение счетного набора множеств меры 0 имеет меру 0, это определение немедленно приводит к теореме о том, что существует набор случайных последовательностей меры 1. Обратите внимание: если мы отождествляем канторово пространство двоичных последовательностей с интервалом [0,1] действительных чисел, мера в канторовом пространстве согласуется с мерой Лебега .

Набор эффективных мер 0 можно интерпретировать как машину Тьюринга , которая способна определить по бесконечной двоичной строке, выглядит ли строка случайной на уровнях статистической значимости. Множество представляет собой пересечение сжимающихся множеств. $U_{1}\supset U_{2}\supset U_{3}\supset \cdots$, и поскольку каждый набор $U_{n}$ задается перечислимой последовательностью префиксов для любой бесконечной двоичной строки, если она находится в $U_{n}$, то машина Тьюринга может за конечное время решить, что струна действительно попадает внутрь $U_{n}$. Следовательно, он может «отвергнуть гипотезу о том, что строка является случайной на уровне значимости». $2^{-n}$«. Если машина Тьюринга может отвергнуть гипотезу на всех уровнях значимости, то строка не является случайной. Случайная строка — это такая строка, которая для каждого вычислимого по Тьюрингу теста случайности умудряется навсегда оставаться неотклоненной на некотором уровне значимости.

Характеристика мартингейла дает интуитивное представление о том, что ни одна эффективная процедура не может принести прибыль, делая ставки против случайной последовательности. Мартингейл д — это стратегия ставок. d читает конечную строку w и делает ставку на следующий бит. Он ставит некоторую часть своих денег на то, что следующий бит будет равен 0, а затем оставшуюся часть своих денег ставит на то, что следующий бит будет равен 1. d удваивает сумму, которую он вложил в бит, который действительно произошел, и теряет остальную часть. d ( w ) — это сумма денег, которую он имеет после просмотра строки w . Поскольку ставка, сделанная после просмотра строки w, может быть рассчитана на основе значений d ( w ), d ( w 0) и d ( w 1), вычисление имеющейся у нее суммы денег эквивалентно расчету ставки. Характеристика мартингейла гласит, что ни одна стратегия ставок, реализуемая любым компьютером (даже в слабом смысле конструктивных стратегий, которые не обязательно вычислимы ), не может принести деньги, делая ставки на случайную последовательность.

последовательностей Мартина-Лёфа

Универсальность

Существует универсальный конструктивный мартингал d . Этот мартингал универсален в том смысле, что для любого конструктивного мартингала d , если d успешен в последовательности, то d успешен и в этой последовательности. Таким образом, d завершается успешно в каждой последовательности в RAND. ^с (но, поскольку d конструктивен, он не завершается успешно ни для одной последовательности в RAND). (Шнорр, 1971)

Существует конструктивное нулевое покрытие RAND. ^с . Это означает, что все эффективные тесты на случайность (то есть конструктивные нулевые покрытия) в некотором смысле подпадают под этот универсальный тест на случайность, поскольку любая последовательность, которая проходит этот единственный тест на случайность, пройдет и все тесты на случайность. (Мартин-Лёф, 1966) Интуитивно этот универсальный тест на случайность говорит: «Если последовательность имеет все более длинные префиксы, которые можно все более хорошо сжимать на этой универсальной машине Тьюринга», то она не случайна» — см. следующий раздел.

Эскиз построения: перечислите эффективные нулевые покрытия как $((U_{m,n})_{n})_{m}$. Перечисление также эффективно (перечисление осуществляется с помощью модифицированной универсальной машины Тьюринга). Теперь у нас есть универсальное эффективное нулевое покрытие за счет диагонализации: $(\cup _{n}U_{n,n+k+1})_{k}$.

Прохождение

Если последовательность не проходит алгоритмический тест на случайность, то она алгоритмически сжимаема. И наоборот, если он алгоритмически сжимаем, то он не проходит алгоритмический тест на случайность.

Схема построения: предположим, что последовательность не проходит тест на случайность, тогда ее можно сжать путем лексикографического перечисления всех последовательностей, не прошедших тест, а затем закодировать местоположение последовательности в списке всех таких последовательностей. Это называется «перечислительным исходным кодированием».

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

Например, рассмотрим двоичную последовательность, выбранную IID из распределения Бернулли. После приема большого количества $N$ образцов, мы должны иметь около $M\approx pN$ те. Мы можем закодировать эту последовательность как «Сгенерировать все двоичные последовательности длиной $N$, и $M$ те. Из них $i$-я последовательность в лексикографическом порядке.».

По Стирлинга приближению $\log _{2}{\binom {N}{pN}}\approx NH(p)$ где $H$ — двоичная функция энтропии . Таким образом, количество битов в этом описании равно:

$$2(1+\epsilon )\log _{2}N+(1+\epsilon )NH(p)+O(1)$$

Первый термин предназначен для префиксного кодирования чисел. $N$ и $M$. Второй термин предназначен для префиксного кодирования числа. $i$. (Используйте омега-кодирование Элиаса .) Третий термин предназначен для префиксного кодирования остальной части описания.Когда $N$ большой, это описание только что $\sim H(p)N$ бит, поэтому он сжимаем со степенью сжатия $\sim H(p)$. В частности, степень сжатия равна ровно единице (несжимаема) только тогда, когда $p=1/2$. (Пример 14.2.8 )

Невозможность системы азартных игр

Основная статья: Невозможность создания азартной системы

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

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

Примеры

• Вероятность остановки Чайтина Ω является примером случайной последовательности.
• Любая случайная последовательность не вычислима.
• Каждая случайная последовательность является нормальной , удовлетворяет закону больших чисел и удовлетворяет всем вычислимым по Тьюрингу свойствам, которым удовлетворяет поток IID равномерно случайных чисел. (Теорема 14.5.2 )

Отношение к арифметической иерархии

• РЭНД ^с ( дополнение к RAND) — это подмножество меры 0 множества всех бесконечных последовательностей. Это подразумевается из того факта, что каждое конструктивное нулевое покрытие покрывает множество с мерой 0, существует только счетное количество конструктивных нулевых покрытий, а счетное объединение множеств с мерой 0 имеет меру 0. Это означает, что RAND является подмножеством с мерой 1 множества. всех бесконечных последовательностей.
• Класс RAND – это $\Sigma _{2}^{0}$ подмножество канторова пространства, где $\Sigma _{2}^{0}$ относится ко второму уровню арифметической иерархии . Это связано с тем, что последовательность S находится в RAND тогда и только тогда, когда в универсальном эффективном нулевом покрытии существует некоторое открытое множество, которое не содержит S ; это свойство можно рассматривать как определяемое с помощью $\Sigma _{2}^{0}$ формула.
• Существует случайная последовательность, которая $\Delta _{2}^{0}$, то есть вычислимое относительно оракула для проблемы остановки. Чайтина (Шнорр 1971) Ω является примером такой последовательности.
• Никакая случайная последовательность не является разрешимой , вычислимо-перечислимой или со-вычислимо-перечислимой . Поскольку они соответствуют $\Delta _{1}^{0}$, $\Sigma _{1}^{0}$, и $\Pi _{1}^{0}$ уровни арифметической иерархии , это означает, что $\Delta _{2}^{0}$ — это самый низкий уровень арифметической иерархии, на котором можно найти случайные последовательности.
• Любая последовательность сводится по Тьюрингу к некоторой случайной последовательности. (Кучера 1985/1989, Гач 1986). Таким образом, существуют случайные последовательности сколь угодно высокой степени Тьюринга .

Относительная случайность

Поскольку каждое из эквивалентных определений случайной последовательности Мартина-Лёфа основано на том, что вычислимо с помощью некоторой машины Тьюринга, естественно задаться вопросом, что же вычислимо с помощью машины-оракула Тьюринга . Для фиксированного оракула A последовательность B , которая не только случайна, но и фактически удовлетворяет эквивалентным определениям вычислимости относительно A (например, ни один мартингал, который является конструктивным относительно оракула A, не достигает успеха на B ), называется случайным относительно к А. ​Две последовательности, хотя сами по себе случайны, могут содержать очень похожую информацию, и поэтому ни одна из них не будет случайной по отношению к другой. Каждый раз, когда происходит редукция Тьюринга от одной последовательности к другой, вторая последовательность не может быть случайной относительно первой, точно так же, как вычислимые последовательности сами по себе неслучайны; в частности, это означает, что Ω Чайтина не является случайной относительно проблемы остановки .

Важным результатом, касающимся относительной случайности, является ван Ламбальгена теорема , которая утверждает, что если C — это последовательность, составленная из A и B путем чередования первого бита A , первого бита B , второго бита A , второго бита. B A и т. д., то C является алгоритмически случайным тогда и только тогда, когда алгоритмически случайным, а B алгоритмически случайным относительно A. является Тесно связанное с этим следствие состоит в том, что если и B сами по себе случайны, то A является случайным относительно B тогда и только тогда, когда B является случайным относительно A. A

Мартина-Лёфа

Относительная случайность дает нам первое понятие, которое является более сильным, чем случайность Мартина-Лёфа, которая представляет собой случайность относительно некоторого фиксированного оракула A . Для любого оракула это по крайней мере столь же сильно, а для большинства оракулов оно строго сильнее, поскольку будут случайные последовательности Мартина-Лёфа, которые не являются случайными относительно оракула A . Важными оракулами, которые часто рассматриваются, являются проблема остановки, $\emptyset '$, и оракул n- го прыжка, $\emptyset ^{(n)}$, поскольку эти оракулы способны ответить на конкретные вопросы, которые возникают естественным образом. Последовательность, случайная относительно оракула $\emptyset ^{(n-1)}$ называется n -случайным; следовательно, последовательность является 1-случайной тогда и только тогда, когда она случайна по Мартину-Лёфу. Последовательность, которая является n -случайной для каждого n, называется арифметически случайной. -случайные последовательности n иногда возникают при рассмотрении более сложных свойств. Например, их всего счетное число. $\Delta _{2}^{0}$ множества, поэтому можно подумать, что они не должны быть случайными. Однако вероятность остановки Ω равна $\Delta _{2}^{0}$ и 1-случайный; только после достижения 2-случайности случайное множество становится невозможным. $\Delta _{2}^{0}$.

Мартина-Лёфа

Кроме того, существует несколько понятий случайности, которые более слабы, чем случайность Мартина-Лёфа. Некоторые из них — слабая 1-случайность, случайность Шнорра, вычислимая случайность, частичная вычислимая случайность. Юнге Ван показал что случайность Шнорра отличается от вычислимой случайности. Кроме того, известно, что случайность Колмогорова-Лавленда не сильнее случайности Мартина-Лёфа, но неизвестно, действительно ли она слабее.

На противоположном конце спектра случайности находится понятие K-тривиального множества . Эти множества являются антислучайными, поскольку весь начальный сегмент логарифмически сжимаем (т. е. $K(w)\leq K(|w|)+b$ для каждого начального отрезка w), но они не вычислимы.

См. также

• Случайная последовательность
• Григорий Чайтин
• Стохастика
• Метод Монте-Карло
• K-тривиальное множество
• Вероятность универсальности
• Статистическая случайность

Дальнейшее чтение

• Игл, Энтони (2021 г.), «Шанс против случайности» , в Залте, Эдвард Н. (редактор), Стэнфордская энциклопедия философии (изд. весной 2021 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено 28 января 2024 г.
• Дауни, Род; Хиршфельдт, Денис Р.; Нис, Андре; Тервейн, Себастьян А. (2006). «Калибровка случайности» . Бюллетень символической логики . 12 (3/4): 411–491. CiteSeerX   10.1.1.135.4162 . дои : 10.2178/bsl/1154698741 . Архивировано из оригинала 2 февраля 2016 г.
• Гач, Петер (1986). «Каждая последовательность сводится к случайной» (PDF) . Информация и контроль . 70 (2/3): 186–192. дои : 10.1016/s0019-9958(86)80004-3 .
• Катчер, А. (1985). «Измерьте, Π ⁰
  ₁ -классы и полные расширения PA». Неделя теории рекурсии . Конспекты лекций по математике. Том 1141. Springer-Verlag. С. 245–259. doi : 10.1007/BFb0076224 . ISBN  978-3-540-39596-6 .
• Кучера, А. (1989). «Об использовании диагонально нерекурсивных функций». Исследования по логике и основам математики . Том. 129. Северная Голландия. стр. 219–239.
• Левин, Л. (1973). «О понятии случайной последовательности». Советская математика — Доклады . 14 : 1413–1416.
• Ли, М.; Витаний, ПМБ (1997). Введение в колмогоровскую сложность и ее приложения (второе изд.). Берлин: Springer-Verlag.
• Мартин-Лёф, П. (1966). «Определение случайных последовательностей». Информация и контроль . 9 (6): 602–619. дои : 10.1016/s0019-9958(66)80018-9 .
• Нис, Андре (2009). Вычислимость и случайность . Оксфордские руководства по логике. Том. 51. Оксфорд: Издательство Оксфордского университета. ISBN  978-0-19-923076-1 . Збл   1169.03034 .
• Шнорр, CP (1971). «Единый подход к определению случайной последовательности». Теория математических систем . 5 (3): 246–258. дои : 10.1007/BF01694181 . S2CID   8931514 .
• Шнорр, Клаус П. (1973). «Сложность процесса и эффективные случайные тесты» . Журнал компьютерных и системных наук . 7 (4): 376–388. дои : 10.1016/s0022-0000(73)80030-3 .
• Чайтин, Грегори Дж . (1969). «О длине программ вычисления конечных двоичных последовательностей: статистические соображения» . Журнал АКМ . 16 (1): 145–159. дои : 10.1145/321495.321506 . S2CID   8209877 .
• Сити, Дж. (1939). Критическое исследование понятия коллектива . Париж: Готье-Виллар.