Метаинформация о свойствах сетевого трафика – это сведения, которые можно извлечь при помощи наблюдения за “поверхностными” особенностями того или иного протокола обмена данными. Самый простой пример – начальное установление соединения: очевидно, что если два узла обменялись начальными пакетами данных, соответствующих схеме некоторого протокола, то, как минимум, в качестве кусочка метаинформации можно записать адреса узлов, тип протокола и метку времени соединения. В моём описании протокола TLS есть небольшой раздел, посвящённый метаинформации о TLS-соединениях. Естественно, принцип подходит не только к TLS, да и далеко не только к IP-сетям или сетям передачи данных вообще. Однако в случае интернет-трафика возникают интересные возможности автоматического обогащения подобных данных.

Даже самые простые сведения, полученные по косвенным сигналам, становятся весьма полезными, если рассматривать последовательности событий. Предположим, что исследуется трафик некоторого центрального сервиса обмена сообщениями через Интернет – приложения-мессенджера. Это приложение работает через центральный сервер, который служит концентратором, пересылающим сообщения между пользователями. Естественно, полезное содержание сообщений зашифровано, возможно, даже с ключами в режиме “точка-точка”. Казалось бы, в такой конфигурации пассивным анализом трафика нельзя обнаружить, какие два пользователя обмениваются сообщениями между собой, потому что все пользователи соединяются с сервером, но не друг с другом напрямую, да и трафик зашифрован.

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

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

Основной момент в том, что если сообщения пишет настоящий пользователь-человек, и пишет их непосредственно в приложение, в диалоговом режиме, то интервалы времени и количество байтов полезной нагрузки, как отпечаток, скорее всего будут транслироваться и в “выходящий канал”, с другой стороны от сервера. И если трафик виден с обоих сторон (входящий и исходящий относительно сервера), то можно попытаться извлечь метаинформацию о том, кто с кем переписывался. Нужно учитывать, что нередко пересылают файлы изображений (сейчас принято то и дело отправлять скриншоты и тому подобные картинки), а это не только увеличивает объёмы трафика, но и создаёт новые сигнатуры, поскольку для доставки изображений мессенджер может использовать дополнительные серверы и дополнительные функции уровня протокола.

Вообще, последовательности (цепочки) некоторых событий, связанных с деятельностью персоны и возникающие в результате применения того или иного отношения порядка – часто уникальны. Отношение порядка тут может быть связано и со временем (открыл приложение “Блокнот”, а через две секунды – приложение “Калькулятор”), и с пространством (проехал базовую станцию “А”, потом базовую станцию “Д” и так далее), а может быть и ещё каким-то – главное, чтобы метки-события выстраивались друг за другом. Потому что тех, кто бывал и в магазине “Мебель”, и в магазине “Стекло”, и в магазине “Богатырь” – гораздо больше, чем тех, кто посетил эти три магазина строго в таком порядке: “Стекло” – “Мебель” – “Богатырь”. Что уж говорить про интервалы времени, взятые “между” магазинами.

Я ранее уже писал на dxdt.ru про идентификацию по цепочкам: например, про применение для деанонимизации мобильных телефонов (2010 год), про идентификацию людей по географическим координатам (2009 год) и не только.



Комментировать »

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



Комментировать »

Sphere in greenПочему лабораторная установка для квантовых экспериментов показывает именно эту статистику? Физика не должна бы отвечать на столь общий вопрос “почему?”. Тем не менее, предположим, статистика такая потому, что через несколько минут две группы исследователей, работающих в одном общем эксперименте, но в разных лабораториях, удалённых одна от другой, сравнят результаты измерений и подставят их в формулу, связанную с неравенством Белла – показатели должны совпасть с уже согласованными ожиданиями.

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

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

Однако если попытаться свести наблюдаемый результат к некоторым заранее принятым допущениям, то легко возникает ощущение некоторой “контринтуитивности” – проступает корреляция, которой, как бы, быть не должно, поскольку, предположим, расставленные в разных и достаточно удалённых точках пространства системы не должны влиять одна на другую мгновенно. Это всего лишь допущения, которые иногда считают некими законами, как в “законах физики”. Видимо, отсюда растёт сравнение с “классической физикой”, приводящее к трактовкам в стиле “если измерить спин одного электрона из пары, то спин второго тут же изменится”. Однако “классическая физика”, что бы это ни значило, тут не должна никак мешать и вообще в процесс включаться.

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

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

С другой стороны, само пространство, выраженное в метриках расстояний, может представлять собой несколько более сложный феномен. Например, более “похожие” объекты находятся ближе. Тогда разнесение (условных) антенн экспериментального оборудования вовсе не означает, что и измеряемые частицы разнесены: дело в том, что для более или менее строгого экспериментального определения расстояния “в пространстве” требуется время, а для времени – требуется опорная частота, но её найти можно не всегда.

Ещё одна занятная лазейка касается “степени случайности” параметров измерений: исследователи, согласно условиям эксперимента, должны выбирать параметры измерений непредсказуемым, для окружающей эксперимент действительности, образом. Предположим, что при создании эксперимента строго определяется не только весь возможный набор результатов измерений, но и действия самих измеряющих. Тогда, опять же, можно получить любую статистику, подходящую под любые неравенства. Устранить этот аспект (обычно, называемый “супердетерминизмом”) не получится – он находится среди допущений, задающих интерпретацию эксперимента. Это позволяет, как минимум, уверенно сохранить “локальность”. Отменяет ли наличие подобного “супердетерминизма” свободу воли исследователей? Нет, не отменяет: исследователи всё так же вольны интерпретировать результаты, а перед этим – планировать серии измерений и технические детали экспериментов, составляя собственное представление о них. Здесь, кстати, кроется один из отличительных аспектов осознания, который никак не вписывается в новомодные системы ИИ с “машинным обучением”.

И это далеко не все онтологические лазейки, связанные с интерпретацией неравенства Белла.

(См. также “Алгоритм Шора и Вселенная кубиками“, “Алгоритм Шора в фантастической машине превращения вероятностей“.)



Комментировать »

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

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

Всё это как раз очень напоминает пифагорейские концепции, описывающие конфигурации явлений окружающей действительности через “сочетаемость” натуральных чисел, происходящую из геометрических свойств этих чисел. И вот оказывается, что тройки решений, удовлетворяющие уравнению Ферма, не вкладываются в набор возможных конфигураций симметрий рациональных чисел. На более техничном языке, конечно, всё звучит сильно загадочнее, даже в первом приближении популярного изложения: эллиптическая кривая, соответствующая упомянутой тройке чисел, не может быть модулярной (Рибет); однако, она должна быть модулярной, потому что все такие кривые – модулярны (это доказательство Уайлса); отсюда и выводится нужное противоречие. Периодические функции, окружности (и диски, кстати), а также разнообразные их логические сочетания, постоянно используются в соответствующем математическом аппарате, но на очень высоком уровне абстракции, поэтому и обозначаются другими терминами, которые с одной стороны – точнее, а с другой – шире. Но конкретно суть доказательства теоремы Ферма, в самом первом приближении, можно представить как невозможность уложить числа в геометрические фигуры. А это подход пифагорейцев, пусть и геометрия используется несколько иная.



Комментировать »

“Демультиплексирование” на общем номере порта TCP протоколов более высокого уровня (TLS/XMPP/SSH и т.п.) при помощи сигнатур начальных пакетов, описываемых регулярными выражениями, имеет и особенности “в другую сторону”: всё, что можно на уровне сокета разобрать (статическим) регулярным выражением на стороне сервера, можно быстро разобрать регулярным выражением и на стороне системы DPI. Естественно, в модели, приписывающей существенный вес номеру порта TCP в классификаторе протоколов, такой программный демультиплексор на серверной стороне был бы достаточно эффективен, но в более широком понимании – метод слишком далёк от стеганографического.



Комментировать »

Ещё немного загадочной типографики, в том числе, про часть буквы “Ё”. Точнее, про “две точки” над этой буквой и занятные совпадения, которые вообще-то с точками не связаны, но пришлись к месту. На скриншоте ниже – небольшой фрагмент манускрипта, датируемого десятым веком н.э. (сам древнегреческий текст – “Жизнь святого Порфирия, епископа Газы”, Марк Диакон, – относится к четвёртому веку, но это здесь не важно, поскольку фрагмент взят только для иллюстрации):
Manuscript copy
Там присутствует буква ипсилон, снабжённая, кроме знака акцента, двумя “точками” (нет, это вовсе не смайлик). Эти две “точки” называются “трема” (или “диерезис”) и вполне себе используются при записи древнегреческого (и даже английского, см. ниже), обозначая разделение гласных. Однако в данном случае дело явно хитрее. В современной типографике соответствующий фрагмент (середина второй строки) выглядит вот так: μετὰ τὸν πρῶτον ὕπνον, что означает “после первого сна”. Над ὕ должен быть знак придыхания, а на рукописном скриншоте знак ударения присутствует отдельно (сверху), соседних гласных нет, так что назначение второй “точки” не ясно. Тем более, что в этом же манускрипте в других сходных случаях двух точек над υ обычно нет, но иногда – встречаются. Это известное, – но какое-то загадочное, – явление, относящееся ещё и к букве ι в манускриптах на древнегреческом. Кстати, “сон” здесь – это тот самый “гипноз”: знак придыхания над ὕ, который объясняет одну “точку”, как раз трансформировался в русское “ги”. А в английском, например, hypnosis.

Трема/диерезис встречается при записи английского, но является большой экзотикой, о которой мало кто знает. Собственно, “Ё” даже в русском-то сейчас используют редко, зато аналогичное, редкое, сочетание знаков есть в английском. Посмотрите: coöperate, сöworker и reëlect. Здесь трема как раз делает “отделяемым” звук, обозначаемый второй буквой. Этот знак тут нужен для того, чтобы не было reel в reëlect и “коровы” (cow) в co-worker. Сейчас, конечно, приём считается устаревшим, а компенсировать можно дефисом.

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



Комментировать »

Green polytopeКвантовая часть алгоритма Шора, если его вообще возможно реализовать, выглядит примерно следующим образом. Первому квантовому регистру назначается состояние, представляющее собой суперпозицию всех входных числовых значений. То есть, предположим, что это 1024 “битовых разряда”, тогда получается 2^1024 различных (числовых) значений и тому подобные штуки. Однако физические детали существенно отличаются, при этом основная идея вообще не касается выбранной реализации. То есть, традиционно, в качестве примера приводят отдельные “кубиты”, как некие “конструкты”, принимающие два состояния (“спин вверх/спин вниз” или что-то похожее, это довольно сложно представить) и совместимые с представлениями о суперпозиции. В квантовой суперпозиции и состоит смысл этих конструктов, так что реализация входного регистра не важна: он является лишь входом, через который основную схему предлагается “подключить”, если хотите, к квантовой ирреальности.

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

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

Если вспомнить математическую часть алгоритма, то речь про вычисление y = A^x (mod M). Обратите внимание на значение A (натуральное число), которое задаёт конкретную схему аппарата для запуска алгоритма Шора! При последовательном вычислении y = A^x (mod M), если показатель x пробегает достаточное количество значений, результат (y) начнёт повторяться, это теоретико-числовая польза от алгоритма, потому что позволяет определить, при каком x A^x == 1 (mod M) и т.д., этому как раз соответствует период данной функции, который мы хотим определить квантовой машиной. Конечно, в случае квантовой машины, никаких подобных вычислений нет: такая машина – супераналоговый прибор, возможно, что ламповый, но скорее холодный, чем тёплый: выход в квантовую ирреальность почему-то требует низких температур. В общем, не предполагается, что происходят какие-то шаги, кто-то переключает реле и сигналы, а на вход “блока функций” поступают разные “иксы”, пусть даже и параллельно. Нет, напротив, подключается несколько миллионов (предположим) загадочных “гейтов”, объединённых в схему, задающую функцию для проверяемого значения A, и всё – предполагается, что в финальном измерении через схему пройдёт поток вероятности, который преобразуется нужным способом и выльется во второй регистр.

Второй регистр тоже можно представлять некоторым единым “бассейном” для входящего потока вероятности, нужного объёма. А можно представлять набором неких кубитов, которых должно быть достаточно много, чтобы получить нужную разрешающую способность. Дело в том, что модели на бумаге можно “записывать” в “действительных числах”, однако, даже если одно действительное число в дополнение к рациональным и влезает в квантовую ирреальность, достать его оттуда полностью точно и за конечное количество измерений – не получится. Это, понятно, не мешает использованию комплексных чисел даже в прикладном квантово-механическом аппарате. Поэтому для окончательного превращения результата в целое число потребуется дополнительно место в пространстве состояний.

Во втором регистре возникает поток вероятности, внутри которого закодирован период ключевой функции, потому что этот поток прошёл через машинерию, реализующую данную функцию. Как физически устроить эту машинерию – не очень понятно. Да и термин “прошёл”, применительно к потоку, тоже достаточно условное обозначение, обусловленное лишь тем, что соответствующие математические формулы в описании будут стоять одна за другой справа.

Машина так устроена, что для этого второго регистра некоторый общий “базис” превращения потока вероятности, который был порядковым или индексным, заменяется на “частотный” – то, что традиционно называется преобразованием Фурье. На графиках это эквивалентно переходу из шаблона, где горизонтальная ось соответствует “времени” (“последовательность событий/состояний”), к шаблону, где горизонтальная ось соответствует частоте (“повторяемость событий/состояний”). Это как раз и есть второй ключевой момент: превращение из индексов в частоты. После этого можно измерять состояние, чтобы получить результат: предполагается, что в выходном регистре, с высокой вероятностью, получится измеренное состояние, которое, используя модель устройства квантовой машины, можно интерпретировать как некоторое значение, кратное периоду функции (детали, связанные с тем, что там должно быть обратное значение, которое ещё не ясно как прочитать и преобразовать, опять же пропускаем). Как это выходное значение будет, так сказать, выглядеть? Например, как набор величин измерений, полученных для каких-то частиц, из которых построен выходной интерфейс. Преобразования, начиная с результатов измерений, уже будут выполняться классическими компьютерами.

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

(См. также про алгоритм Шора и Вселенную кубиками.)



Комментировать »

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

Понятно, что какие-то прямые физические воплощения для такого числа придумать не получится, поскольку, например, 2^1024 несравнимо больше, чем масса Земли, подсчитанная в граммах. Но можно пойти на комбинаторные ухищрения. Нарежем пространство Вселенной на 2^80 небольших кубиков. 2^80 выглядит очень похожим на разные оценки “объёма Вселенной”, “количества частиц” и других сходных параметров. Перестановкой этих кубиков можно получать разные конфигурации Вселенной, которые, возможно, будут весьма сходными. Предположим, что количество конфигураций это (2^80)! (факториал, а не восклицание). “Реальный”, – что бы это ни значило, – показатель может быть другим: нужно учитывать возможности по сочетанию получившихся кубиков, их взаимное расположение. Однако для нашего примера это не важно.

Существенно ли (2^80)! превосходит 2^1024? Может показаться, что 2^1024 очень большое число. Однако провести сравнение нетрудно. Заметьте, что при вычислении факториала каждое чётное число повышает степень двойки (иногда – больше чем на единицу), поэтому 2^1024 вкладывается уже в 1026! (ну или примерно так; 1026 = 1024+2, проверьте; естественно, 171! больше 2^1024). Что уж говорить про (2^80)!! (Здесь второй восклицательный знак обозначает восклицание.) Теперь может показаться, что 2^1024 не такое уж и большое число, чтобы не вкладываться в качественно нарезанную Вселенную.

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

Но, конечно, если Вселенная является симуляцией, то мощностей на 2^1024 состояний может и не хватить. А ведь не исключено, что получение нужной для 1024 битов разрешающей способности может потребовать во много раз больше кубитов, а элементов квантовой схемы – так вообще миллионы могут понадобиться. Впрочем, в симуляции факторизация скорее всего известна заранее: выписать на листке подобранное вручную 1024-битное простое число, удерживая его в области внимания, довольно трудно, а все остальные способы получения больших простых чисел, предположим, представляют собой результат спуска подготовленного значения из машины симуляции вселенных (из гипервизора, так сказать). Да что уж там – даже и выписывание числа может быть “наведённым”: ведь ещё предстоит проверить его простоту (спускается ли структура простых из машины симуляции в симуляцию?).

Так или иначе, но выходит, что реализация квантового алгоритма факторизации выдвигается во внешнюю область, которая не определяется окружающей “физической реальностью”, но объекты из этой области могут в “физическую реальность” проваливаться. Однако считается, что удерживать схему из кубитов там сложно, поэтому элементы достаточно быстро должны бы входить в зацепление с “реальностью”, теряя, тем самым, возможности для эффективной работы. В физике это называется декогеренцией, а для наших целей можно считать, что “категория”, стоящая за квантовым вычислением, “запутывается” (entanglement) с той действительностью, о которой смогли договориться наблюдатели – то есть, локализуется или схлопывается, теряя все полезные свойства. Иногда результатом локализации может быть “результат вычислений”. Хотя, вычисления ли это? Отдельный вопрос.



Комментарии (1) »

TypewriterГенераторы текстов на заданную тему сейчас вновь популярны. Пример, естественно, ChatGPT. Можно ли автоматическим способом и с высокой точностью определить, что некоторый обозримый текст на естественном языке написан таким качественным компьютерным генератором, а не человеком?

Если эту задачу рассматривать “в максимальной общности”, то она тут же превращается в весьма занятную, почти что философскую, проблему: допуская, что можно надёжно различить тексты, написанные подобной программой и человеком, придётся допустить и то, что программа может выдать текст, который человек написать не смог бы – не смог бы сымитировать. То есть, в тексте, который написал генератор текстов, должно быть проявление некоторого “нечеловеческого интеллекта”.

С одной стороны, внутреннее устройство новомодных больших компьютерных нейросетей уже достаточно необозримо. Эти сети состоят из мешанины формул (по-научному – из “мешанины функционалов”, но в данном случае можно называть объект просто формулой). Разобраться, что и как взвешивается и преобразуется во всей этой мешанине, для человека, “вручную”, не реально. Можно предположить, что перспективная программа-детектор как раз и могла бы обнаружить в тексте проявление всех этих глубинных взаимосвязей, заведомо недоступных для интерпретации и имитации человеком, классифицировав таким образом текст как созданный ИИ. Именно из сходных соображений детекторы сейчас пытаются делать на основе обучения всё тех же (а точнее – таких же) нейросетей. Но точность не велика. А вырожденный результат на этом направлении – это так называемые “водяные знаки” (watermark), которые разработчики нейросетей планируют вводить в результат их работы, как раз с целью последующего точного распознавания.

С другой стороны, такой подход чем-то напоминает объявление числа Пи (π – но с заглавной буквы) самым разумным числом из всех: ведь “в десятичной записи числа Пи можно найти любой текст, с ответами на любые вопросы, как бы этот текст ни зашифровали”, нужно только знать, с какого знака записи начинать читать – вроде и верно, но не слишком-то конструктивно (напоминает классические теоремы существования, времён Коши, а также и саму теорию действительного числа). Но программа, которая позволила бы находить проявления некоторого необозримого ИИ в небольшом, если сравнивать с количеством коэффициентов в формулах нейросети, тексте на естественном языке, сама может оказаться столь же необозримой. А значит, к ней применимы те же рассуждения, и соответствующий процесс вряд ли быстро сойдётся.

При этом, скорее всего, каждый естественный язык является проявлением общей универсальной структуры, которая не может быть видна из “плоской”, – пусть при этом и слоистой, – статистики слов и словосочетаний, построенной алгоритмом (Хомский и др.). А это оставляет большие шансы для успешной имитации человеком текстов, которые универсальная программа-детектор могла бы, при прочих равных, посчитать результатом работы компьютерной нейросети.

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

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

Так что, к сожалению, высокоточные детекторы “текстов от нейросетей” вряд ли появятся. Кроме, конечно, детекторов, которые работают на “водяных знаках” – специальных криптографических метках.



Комментарии (1) »

На картинке ниже – фрагмент текста из книги “Изложение алгебры” (или, если хотите, “Трактат об алгебре”), Джона Валлиса: John Wallis, A TREATISE OF ALGEBRA, both historical and practical. Год издания, обратите внимание, 1685.

На первый взгляд, в тексте присутствуют “смайлики”, собранные из символов “;”, “:” и “)”. То есть, один “смайлик” – подмигивающий.

Естественно, это не “смайлики”, что очевидно из контекста. Такие сочетания символов – особенности старой типографики (и, возможно, синтаксиса): размещение знаков пунктуации внутри скобок подобным образом тогда являлось обычной практикой (и, кстати, обратите внимание на буквы и орфографию). В качестве дополнительной иллюстрации – “фотография” автора книги и титульный лист.

(Источник изображений: Google Books.)



Комментировать »

Bartolomeu Velho, 1568; WikimediaЕсли выбрать систему координат таким образом, что Солнце движется в ней прямолинейно со скоростью несколько сотен км/сек., то траектория Земли окажется кривой, напоминающей синусоиду. В этой системе координат Земля вовсе не “вращается вокруг Солнца”, в том “наивном” смысле, что не описывает окружность, в центре которой Солнце.

Для навигации на поверхности Земли – удобны другие системы координат, в которых Солнце вращается вокруг Земли, поскольку она зафиксирована. Расхожее утверждение, что “Земля вращается вокруг Солнца” – не более чем фигура речи, пусть и очень популярная. Например, для того, чтобы получить существенные вычислительные преимущества при предсказании астрономических событий Солнечной системы, наблюдаемых с Земли, самой по себе гелиоцентрической системы не достаточно, нужно ещё учитывать геометрию орбит планет, иначе потребуется, как и в развитом геоцентрическом случае, вводить множество дополнительных “параметров”, чтобы наблюдения как-то сходились с моделью.

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

Вернёмся к движению планет. То, что Солнце существенно больше Земли, а наблюдаемое движение светила по небу можно объяснить при помощи модели, в которой именно Земля движется вокруг, выяснили ещё древние греки. Но, скажем, измерение годичного параллакса звёзд, как подтверждение движения Земли по орбите, удалось произвести только в 19 веке. Следует ли считать, что до этого момента утверждение “Земля вращается вокруг Солнца” было всего лишь популярным обобщением? Нет, конечно. Это утверждение, в изолированной форме, и сейчас не несёт особого смысла. То есть, процесс выбора моделей мира был длительным, непростым, и не сводился к тому, как сейчас нередко принято объяснять: “Коперник открыл, что Земля вращается вокруг Солнца”. Никаких особенных причин утверждать, что именно Земля движется, нет, а практическое удобство гелиоцентрических систем совсем в другом.

Но главное полезное наблюдение состоит не в этом. Так, в разных системах отсчёта, в разных системах координат, движение светил будет описываться различными формулами, которым соответствуют различные траектории. Результаты нередко выглядят неожиданными: например, траектория Луны, движушейся вокруг Солнца, очень близка к окружности. Действительно, от одной формулы можно перейти к другой. Именно на этом уровне и образуется новое знание, отличающееся от простого заучивания кратких “утверждений”. Это знание позволяет понять, почему разные системы отсчёта, представленные в наивном виде (“Земля вращается вокруг Солнца”), как бы “противоречат” друг другу. То есть, знание, – по крайней мере, математическое, – здесь соответствует механизму разрешения противоречий. Этот механизм находится на пару уровней выше утверждения “Земля вращается вокруг Солнца”. Естественно, астрономические успехи связаны с определением и строгим формулированием элементов этого механизма. На первом этапе – понимание того, что наблюдаемая картина движения светил может быть интерпретирована различными способами. На втором – создание логических конструкций, позволяющих вычленить существенные характеристики того, как различные модели переходят одна в другую, с сохранением наблюдаемого результата. И уже на третьем этапе – выяснение причин такого перехода и их строгое описание. Простое утверждение “Солнце вращается вокруг Земли” не играет сколь-нибудь значительной роли, гораздо важнее понимание того, что подразумевается под “вращением”, насколько это понятие универсально.



Комментировать »