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

39

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

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

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

Джозеф О'Рурк
источник
1
Это помогает, если вы сначала рассмотрите определение «действительно случайный».
MS Dousti

Ответы:

52

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

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

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

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

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

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

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

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

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

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

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


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

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

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

LaurentBienvenu
источник
8
какой красивый ответ.
Суреш Венкат
1
Я очень благодарен за ясность вашего подробного ответа на этот (для меня!) Запутанный вопрос. Благодарность!
Джозеф О'Рурк
12

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

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

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

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

Аарон Стерлинг
источник
11

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

Ян
источник
Ссылка на книгу здесь: amazon.com/…
Суреш Венкат
Спасибо, Ян и Суреш, я забираю эту книгу из нашей библиотеки!
Джозеф О'Рурк
Еще одна замечательная книга Ниса "Вычислимость и случайность".
Диего де Эстрада
11

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

Jeffε
источник
Ха! Отличная цитата, Джефф! И с предметным пунктом.
Джозеф О'Рурк
7

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

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

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

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

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

fi(x,r)fir

Робин Котари
источник
Я нахожу это проницательным: «Если нет, то DTM должен дать правильный ответ, независимо от того, какие случайные биты были предоставлены». Благодарность!
Джозеф О'Рурк
На самом деле я не понимаю этого. Вы, кажется, предполагаете, что P = ZPP или что рандомизированный алгоритм с нулевой ошибкой (например, алгоритм Лас-Вегаса) должен быть детерминированным?
Суреш Венкат
Используя DTM с доступом к оракулу в качестве языка, я предположил, что DTM останавливается через некоторое время. В этом случае мы можем избавиться от оракула. Для нулевой ошибки мы просто заменим его на 0000 ..., а для любой другой цели можно использовать грубую силу для всех случайных строк конечной длины. (Я уверен, что кто-то, вероятно, придерживается мнения, что алгоритмы Лас-Вегаса на самом деле не являются алгоритмами, поскольку они не обязательно заканчиваются.)
Робин Котари
5

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

Аарон Стерлинг
источник
Просто чтобы уточнить: хотел ли Джо случайный оракул (который по сути является случайной хэш-функцией) или просто источник случайности? это не одно и то же?
Суреш Венкат
Спасибо, Аарон, упоминание иерархии оракула случайности полезно.
Джозеф О'Рурк
@ Суреш: я имел в виду источник случайности.
Джозеф О'Рурк
Вы оба, вероятно, далеко впереди меня здесь, но я пытался сказать, что случайность должна быть определена относительно «системы отсчета», то есть ресурсов, доступных для предсказаний. «Источник случайности» может быть случайным по отношению к машине Тьюринга, но не по отношению к Остановляющему Оракулу. Я согласен с ответом Робина Котари; Я только хотел сказать, что «чистый источник случайности», по-видимому, не существует в современных определениях, потому что мы всегда можем диагонализировать его и получить что-то случайное.
Аарон Стерлинг
5

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

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

Суреш Венкат
источник
Этот результат для алгоритмов полиномиального времени, верно? Я интерпретировал вопрос ОП как вопрос о теории вычислимости, а не о теории сложности. Под этим я подразумеваю, что интерпретировал это так: «Является ли набор проблем, решаемых источником случайности DTM +, большим, чем проблемы, решаемые DTM?»
Робин Котари
это возможно. Отсюда моя попытка объяснить это более подробно. На уровне вычислимости несоответствие могло бы сделать недействительным тезис Черча-Тьюринга.
Суреш Венкат
Мне нравится этот объемный пример! Хотя я специально спросил о теории вычислимости, меня также интересуют различия в сложности. Я не понимаю, как это могло бы сделать КТ недействительной, потому что предыдущие ответы устанавливали, что чистый источник истинной случайности не вычислим ...?
Джозеф О'Рурк
Я думаю, что как только мы формализуем то, что мы подразумеваем под DTM с доступом к источнику случайности (с его критериями приемлемости, вероятностью остановки и т. Д.), Мы сможем показать, что эта модель также точно вычисляет рекурсивные языки.
Робин Котари
Верно (в области comutable). Но теперь я задаюсь вопросом: предположим, что мы создаем строку, чей i-й бит является результатом запуска i-й машины Тьюринга в самой кодировке. Будет ли возможность предсказать эту строку в соответствии с решением проблемы Остановки, и является ли эта строка случайной в смысле Мартина-Лофа?
Суреш Венкат