Действительно генератор случайных чисел: вычислимый по Тьюрингу?

Я ищу окончательный ответ на вопрос, является ли генерация «действительно случайных» чисел вычислимой по Тьюрингу. Я не знаю, как точно сформулировать это. Этот вопрос StackExchange об «эффективных алгоритмах генерации случайных чисел» близок к ответу на мой вопрос. Чарльз Стюарт говорит в своем ответе: «Это [случайность Мартина-Лёфа] не может быть сгенерировано машиной». Росс Снайдер говорит: «Любой детерминистический процесс (такой как машины Тьюринга / Регистра) не может производить« философские »или« истинные »случайные числа». Есть ли четкое и общепринятое представление о том, что представляет собой генератор действительно случайных чисел? И если да, то известно ли, что оно не может быть вычислено машиной Тьюринга?

Возможно, достаточно указать мне соответствующую литературу. Спасибо за любую помощь, вы можете предоставить!

Редактировать. Спасибо Яну и Аарону за знающие ответы! Я относительно не обучен в этой области, и я благодарен за помощь. Если можно немного расширить вопрос в этом приложении: это тот случай, когда TM с доступом к чистому источнику случайности (оракулу?) Может вычислить функцию, которую не может классический класс?

Я довольно поздно присоединяюсь к обсуждению, но постараюсь ответить на несколько вопросов, которые были заданы ранее.

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

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

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

Бесконечная двоичная последовательность является случайной по методу Мартин-Лёфа, если никакой вычислимый процесс (даже если мы позволим этому процессу быть вычисляемым за три или более экспоненциальное время) не сможет обнаружить дефект случайности.$\alpha$

(1) Что мы подразумеваем под «ошибкой случайности»? Эта часть очень проста: это множество меры 0, то свойство , что почти все последовательности не имеют (здесь мы говорим о Лебеге то есть мера , где каждые биты имеет вероятность быть 0 независимо от всех остальных биты). Примером такого недостатка является «асимптотически 1/3 нулей и 2/3 единиц», что нарушает закон больших чисел. Другой пример: «для каждого n первые 2n бит α идеально распределены (столько нулей, сколько единиц)». В этом случае закон больших чисел утверждается, но не центральная предельная теорема. И т. Д.$1/2$$0$$\alpha$
(2) Как вычислимый процесс может проверить, что последовательность не принадлежит определенному набору меры 0? Другими словами, какие множества меры 0 можно вычислить вычислимо? Это именно то, о чем говорят тесты Мартина-Лёфа. Тест Мартина-Лёфа - это вычислимая процедура, которая при заданном входном значении k вычислимо (т. Е. Через машину Тьюринга с входным значением ) генерирует последовательность строк w k , 0 , w k , 1 , ..., такую ​​что множество U k бесконечных последовательностей, начинающихся с одного из этих w k , i имеет меру не более 2 - $k$$w_{k,0}$$w_{k,1}$$U_k$$w_{k,i}$$2^{-k}$(если вам нравится топология, обратите внимание, что это открытый набор в топологии продукта для набора бесконечных двоичных последовательностей). Тогда множество имеет меру 0 и называется нулевым множеством Мартина-Лёфа . Теперь мы можем определить случайность Мартина-Лёфа, сказав, что бесконечная двоичная последовательность α случайна по Мартину-Лёфу, если она не принадлежит ни к какому нулевому множеству Мартина-Лёфа . $G=\bigcap_k U_k$$0$$\alpha$

Это определение может показаться техническим, но оно широко признано правильным по нескольким причинам:

• он достаточно эффективен, то есть его определение включает в себя вычислимые процессы
• оно достаточно сильное: любое «почти уверенное» свойство, которое вы можете найти в учебнике по теории вероятностей (закон больших чисел, закон повторного логарифма и т. д.), может быть проверено с помощью теста Мартина-Лёфа (хотя это иногда трудно доказать)
• он был независимо предложен несколькими людьми, использующими разные определения (в частности, определение Левина-Чейтина, использующее колмогоровскую сложность); и тот факт, что все они приводят к одному и тому же понятию, является намеком на то, что оно должно быть правильным понятием (немного похоже на понятие вычислимой функции, которая может быть определена с помощью машин Тьюринга, рекурсивных функций, лямбда-исчисления и т. д.)
• математическая теория очень хороша! см. три превосходных книги «Введение в колмогоровскую сложность и ее приложения» (Ли и Витани), « Алгоритмическая случайность и сложность» (Дауни и Хиршфельдт), « Вычислимость и случайность» (Ниес).

Как выглядит случайная последовательность Мартина-Лёфа? Ну, возьмите идеально сбалансированную монету и начните ее подбрасывать. На каждом сальто напишите 0 для голов и 1 для хвостов. Продолжайте до конца времени. Вот как выглядит последовательность Мартина-Лёфа :-)

Теперь вернемся к первоначальному вопросу: существует ли вычислимый способ генерирования случайной последовательности Мартина-Лёфа? Интуитивно, ответ должен быть НЕТ , потому что, если мы можем использовать вычислимый процесс для генерации последовательности , то мы, безусловно, можем использовать вычислимый процесс для описания синглтона { $\alpha$$\alpha$ }, поэтому не является случайным. Формально это делается следующим образом. Предположим, что последовательность α вычислима. Рассмотрим следующий тест Мартина-Лёфа: для всех k просто выведите префикс a k из α длины k и ничего больше. Это имеет меру не более (фактически, точно) 2 - $\alpha$$\alpha$$k$$a_k$$\alpha$$k$$2^{-k}$и пересечение множеств как в определении, в точности равно { α }. QED !!$U_k$${\alpha}$

На самом деле случайная последовательность Мартина-Лёфа неисчислима в гораздо более сильном смысле: если какое-то вычисление оракула с оракулом β (которое само является бесконечной двоичной последовательностью) может вычислить α , то для всех n , n - O ( 1 ) битов β необходимы для вычисления первых n битов α (на самом деле это характеристика случайности Мартина-Лёфа, которая, к сожалению, редко указывается, как в литературе).$\alpha$$\beta$$\alpha$$n$$n-O(1)$$\beta$$n$$\alpha$

Хорошо, теперь часть «редактирования» вопроса Джозефа: это тот случай, когда TM с доступом к чистому источнику случайности (оракулу?) Может вычислить функцию, которую не может классический класс?

С точки зрения вычислимости ответ - «да и нет». Если вам предоставляется доступ к случайному источнику в качестве оракула (где выходные данные представлены в виде бесконечной двоичной последовательности), с вероятностью 1 вы получите случайный оракул Мартина-Лёфа, и, как мы видели ранее, случайный случай Мартина-Лёфа подразумевает вычислимо, так что достаточно вывести самого оракула! Или, если вам нужна функция , вы можете рассмотреть функцию f, которая для всех n сообщает вам, сколько нулей есть среди первых n бит вашего оракула. Если оракул случайный по Мартину-Лёфу, эта функция будет невычислимой.$f: \mathbb{N} \rightarrow \mathbb{N}$$f$$n$$n$

Но, конечно, вы можете утверждать, что это обман: на самом деле, для другого оракула мы можем получить другую функцию, поэтому возникает проблема с невоспроизводимостью. Следовательно, другой способ понять ваш вопрос заключается в следующем: есть ли функция которая не вычислима, но которая может быть «вычислена с положительной вероятностью», в том смысле, что существует машина Тьюринга с доступом к случайному оракулу, который, с положительной вероятностью (над оракулом) вычисляет f . Ответ - нет, из-за теоремы Сакса, доказательство которой довольно просто. На самом деле на это в основном ответил Робин Котари: если вероятность того, что ТМ будет правильной, больше 1/2, то можно искать все n во всех возможных вычислениях оракула с помощью ввода $f$$f$$n$$n$и найдите результат, который получает «большинство голосов», то есть который создается набором оракулов меры более 1/2 (это можно сделать эффективно). Аргумент даже распространяется на меньшие вероятности: предположим, что ТМ выводит $f$ с вероятностью . По теореме плотности Лебега существует конечная строка σ такая, что если мы зафиксируем первые биты оракула как точно σ , а затем получим другие биты случайным образом, то мы вычислим f с вероятностью не менее 0.99. Взяв такое σ , мы можем снова применить приведенный выше аргумент.$\epsilon >0$$\sigma$$\sigma$$f$$\sigma$

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

В этом контексте тест Мартина-Лофа можно рассматривать как детерминированный процесс, а определение случайной последовательности является именно той последовательностью, поведение которой не предсказывается никаким вычислимым / детерминированным процессом Мартин-Лофа.

Это, однако, вызывает вопрос: «Эффективно ли вычисляется случайная последовательность в реальной жизни?» На самом деле здесь есть индустрия. Существуют опубликованные компакт-диски с миллиардами случайных (?) Битов, которые используются для компьютерного моделирования физических систем и т. Д. Эти компакт-диски гарантируют, что их последовательности битов пройдут ряд тестов Мартина-Лофа. В книге « Путь пьяницы: как случайность управляет нашими жизнями» дается подробное объяснение этой проблемы в поп-науке.

Нерелевантный момент: мне нравится твоя колонка. :-)

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

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

Кажется, никто не ответил на ваше приложение, поэтому я попробую:

Если можно немного расширить вопрос в этом приложении: это тот случай, когда TM с доступом к чистому источнику случайности (оракулу?) Может вычислить функцию, которую не может классический класс?

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

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

Так разрешено ли ТМ с доступом к случайности совершать ошибки? Если нет, то DTM должен дать правильный ответ, независимо от того, какие случайные биты были предоставлены. В этом случае случайные биты не нужны, так как вы можете просто взять случайную строку равной 00000 ...

$f_i(x,r)$$f_i$$r$

Относительно вашего «вопроса редактирования»: это имеет большое значение, если вы спрашиваете о вычислимости или сложности. Если на ТМ есть границы сложности, то вы получите так называемую модель случайного оракула . Если ТМ может использовать произвольно большие, но конечные ресурсы, то вы находитесь в мире относительной случайности : существуют иерархии случайностей оракулов, так же, как и степени Тьюринга. (Дополнительный момент: одна из (не) знаменитых статей Коблица и Мензеса была посвящена использованию модели случайного оракула, поэтому ваш мета-вопрос касается недавних академических дебатов.)

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

Мы знаем, что существует безусловный результат невозможности приближения к субэкспоненциальному коэффициенту объема выпуклого тела детерминистически (это старый результат Барани и Фюреди ). Напротив, мы можем получить FPRAS для этой проблемы, используя выборку. Это пример разделения, которое вы ищете?