Юмор

[offtop]

"Испанские ученые создали генератор действительно случайных чисел"

Чтобы обойти эту проблему, Антонио Асин, физик из Института фотонных наук (Барселона), и его коллеги разработали тест на истинную случайность, который возвращает нас к историческим экспериментам по природе квантовой механики, впервые предложенным физиком Джоном Беллом в 1960-х годах. Белл хотел подтвердить, что классическая физика не может объяснить странные свойства связанных частиц (entangled particles), которые связаны так, что измерение одной непосредственно влияет на состояние партнера. Ученый рассчитал максимально возможный уровень корреляции между двумя частицами в любой классической системе. Последующие эксперименты неоднократно подтверждали, что связанные частицы превышают этот предел вопреки классической физике.

Завидую секлабу. Они пишут, и им всё понятно, а я читаю и из-за каждого предложения возникают вопросы "почему". Два часа обсуждал этот абзац с одним физиком, кое-как прояснилось что имелось в виду и почему это верно. Казалось бы... причём тут классическая физика к неравенствам Белла? Их нарушение – свойство функции распределения, т.е. обычная теория вероятности, захотел – создал какое хочешь распределение, и не нужны для этого квантовые частицы. В простейшем случае можно написать программу :)
[/offtop]

В простейшем случае можно написать программу :)

spinore, Вы тоже ничего не понимаете в доказуемой безопасности! © :)

Ничего вы не понимаете в доказуемой безопасности! :-)
Зато эти числа доказуемо безопасны по каким-то квантовым критериям (м.б. spinore раскопает оригинал и объяснит). Получающиеся числа должны быть неотличимы от идеального случайного источника (если аппаратура правильно осуществляет контроль квантовых состояний) и они не требуют постобработки и хэширования.

spinore, Вы тоже ничего не понимаете в доказуемой безопасности! © :)

Терпение и спокойствие, сейчас [сегодня] ответ появится, занят обсуждением со специалистами :-)

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

Здесь есть два важных момента: случайные числа с точки зрения математики (белый шум, равномерная плотность вероятности и т.д.) и с точки физики (максимально случайные числа, которые можно извлечь из каких-то физических приборов). Если с первым всё ясно, то со вторым – всё очень трудно, и всё упирается в вопрос их практического получения. Попутно замечу, что статистическими тестами отличить псевдослучайную последовательность произвольной конечной длины n от истино случайной нельзя [в строгом математическом смысле], поэтому нужно ориентироваться на какие-то другие критерии случайности.

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

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

Существуют слухи в научном сообществе о том, что не всякий гамильтониан [и квантовое состояние?] может быть реализован на практике, но это утверждение совершенно недоказанное. Однако, допустим, что квантовая теория – не самая фундаментальная, а лишь является [статистикой?] относительно какой-то более фундаментальной теории Y, тогда мы бы [вполне возможно] имели тот случай, когда в Y реализуется более богатый класс функций распределения, чем в квантовой механике, и случаные числа в Y были бы более идеальными [иронизируя по поводу терминологии статьи], но, т.к. квантовая механика всё же пока считается самой всеобъемлющей теорией, надеяться на получение "более случайных" чисел на практике не получится [из спуреструн в момент большого взрыва?].

Кстати, вспонил: можно формально определить такие функции распределения (называются "суперскоррелированные состояния"), которые не реализуемы ни в квантовой (нарушают положительную определённость в представлении через матрицы плотности, кажется), ни в классической механике [в классической механике неравенства Белла дают ограничение в 2, в квантовой – 2sqrt(2), а суперскоррелированные – 4], из чего следует(?), что даже квантовая механика не даёт полной случайности, так что... закапывайте ваши случайные числа.

P. S.: Это ответ в виде "усреднения по ансамблю из 2ух физиков", а потому на истину в последней инстанции точно не претендует :) Для особо жаждущих по ссылке приведены логи обсуждений темы по jabber'у с Vadim_Z и словарь-минимум к ним, где подробно рассматривается вопрос и показано, что на самом деле всё очень и очень не просто :=( [по крайней мере, для моих мозгов].

Если так, то всё доказательство рассыпается, даже если оно интересно только для теории.
Но ведь 42 случайных числа они явно генерировали целый месяц, чтобы что-то этим продемонстрировать. Если ни один из известных науке физических процессов не способен давать идеальные случайные числа в чистом виде, то что тогда?

тогда слегка трезвая машинистка

м.б. spinore раскопает оригинал и объяснит

Вот оригинал. Ещё ссылки из жёлтой прессы: раз, два. Вроде как авторы получили некоторую оценку, из которой явствует, что если система что-то мерит для состояния, нарушающего неравенства Белла, то при очень широких предположениях можно гарантировать некоторую степень рандомности. При этом прибор может быть с памятью, может быть асимметрия измерений и т.п. Ещё утверждается, что на "классических состояниях" такой гарантии дать нельзя. А по-хорошему, надо читать и вникать, чтобы понять кто прав/виноват и почему.

можно формально определить такие функции распределения (называются "суперскоррелированные состояния"), которые не реализуемы ни в квантовой (нарушают положительную определённость в представлении через матрицы плотности, кажется), ни в классической механике

Неравенства Белла в контексте этих трёх случаев достаточно внятно описаны в этой статье, на 11ой стр. показан пример распределения, которое никогда реализуется ни в классике, ни в квантах.

Если ни один из известных науке физических процессов не способен давать идеальные случайные числа в чистом виде, то что тогда?

Что такое "идеально случайное" число? Есть ли вообще такое понятие в математике? Я могу взять любую последовательность нулей и единиц, записать её в десятичном формате и спросить что-то вроде: 56384 – это случайное число? Для любого набора тестов "идеальной случайности" можно построить такой ГПСЧ, что все тесты будут пройдены. Обратное тоже верно – для любого ГПСЧ можно придумать такой набор тестов, что тот его не пройдёт. Все статистические тесты принципиально конечны, поэтому их можно обмануть. Есть и другая сторона той же монеты – можно взять последовательность из ста выпаданий орлов, которая обязательно вылезет, если кидать очень долго. Если применить статтест к такой последовательности – она не будет случайной. Вполне возможно, что всё это вопросы вычислительной сложности, т.е. существующие статтесты покрывают существующие ГПСЧ. Вся случайность – это наша вера в неё, если быть последовательным статистиком. Про то, что нечто случайно, можно рассуждать только как о постулате.

Можно ещё так сказать. Есть 2 типа случайности: случайность самой "случайной величины" и случайность её функции распределения. "Истиная случайность" в смысле авторов, видимо, относится ко второму типу: случайная величина со случайно выбранной функцией распределения. На практике приходится работать не с самими случайными величинами, а с выборками, при этом принципиально точно не известно распределение, которому они соответствует (можно только строить оценки). В свою очередь выборка длины n есть n случайных величин, и можно ставить вопрос об их зависимости и корреляциях. Дальше начинаются такие дебри... я некомптентен и уже всё забыл что и знал.

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

Тут мог бы пролить свет специалист, кто хотя бы профессионально понимает теорию вероятности. Я к таким не отношусь, поэтому вся надежда на unknown'а.

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

[предварительные мысли по поводу]

Ещё утверждается, что на "классических состояниях" такой гарантии дать нельзя.

В их логике примерно так получается. Если есть монетки с какой-то вероятностью выпадания орла и решки, то по самой последовательности выборок ничего сказать [строго говоря] нельзя. Однако, если неравенства Белла нарушаются, то энтропия не может быть меньше некоторой величины [опять же, справедливо только для случаев типа монеток]. Т.е. для таких "квантовых" функций распредления, из-за их свойства нарушения неравенств Белла, можно получить оценку на энтропию, из которой, в свою очередь, следует, что числа не могут быть не случайными, причём минимальная "степень их случайности" оценивается.
[/предварительные мысли по поводу]

[offtop]

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

Это в практическом. А в теоретическом... Вот взять хотя бы конспективное изложение одной лишь аксиоматики, которая нужна, чтобы корректно определить что же есть [в общем случае] всем "интуитивно понятная" вероятность. И пошло поехало: сигма-алгебры, сигма-аддитивность, алгебра событий, понятие меры [а раз мера, значит понятие измеримости (естественно, по Лебегу), примеры неизмеримых множеств (вообще жуть, модели математики для математики: то, чего якобы нет), меру не рассказать без основ теории множеств (тоже хардкор)]. Получается такой сбитый курс, где всё необходимое для понимания пытаются ввести по ходу дела, ибо общей математической культуры нет. Достаточно сказать, что в стандартную университетскую программу подготовки физиков этот курс (стохастические процессы) не входит, вместо него дают "основы теории вероятности", где всё можно объяснить на пальцах на школьном уровне. У нас на факультете мой курс был последним, кому это всё пытались читать, а потом сняли, ибо "сложно, да и ни к чему этим прикладникам-экспериментаторам".
[/offtop]

Мда. Ведь даже название предмета (http://slovari.yandex.ru/dict/.....icle/00012/89300.htm) выучить не смогли :)

А. Пуанкаре Случайность
Ю. В. Чайковский Что такое случайность?

Вполне возможно, что всё это вопросы вычислительной сложности

Да, трудновычислимые функции труднопредсказуемы ;)
О сложности по Колмогорову, см. ссылки в обсуждении.

Афоризмы о случайности, тут и тут

Кстати, для юмора нужен именно неожиданность поворота сюжета. Так что разговор здесь о случайности – не совсем оффтоп :)

О сложности по Колмогорову, см. ссылки в обсуждении.

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

Правильная ссылка: А. Пуанкаре. Случайность, глава 4 из его книги Наука и метод

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

– Дети, напишите предложение:"Вороне где-то Бог послал кусочек сыра"
– Марьванна, а бога нет!
– Сыра тоже нет... Что же, тепеь и диктант не писать?
(Анекдот конца 80x)

Сегодня ночью снится: вижу какой-то старый топик с предыдущих лет на pgpru под названием

Криптозоология в д. хоз.

(в домашнем хозяйстве – сокр.). Думаю, что за фигня такая. Говорю SATtva'е:
- Это вообще не по теме сайта. Может быть снести?
- Можно и снести.
P.S.: надо меньше pgpru читать :) Для любознательных: http://ru.wikipedia.org/wiki/Криптозоология

Воображение рисовало страшные картины "Криптозоотехники в проведении криптозооанализа" и др. Каких только кошмаров не бывает :)